C++ · Kontenery STL · Mapa

Mapy (map) w C++

Poznaj kontener map — strukturę przechowującą pary klucz → wartość, automatycznie posortowaną według klucza. Zamiast szukać po indeksie, szukasz po własnym kluczu.

Filmy z OKI

Wolisz obejrzeć?

Olimpijskie Koło Informatyczne nagrywa swoje zajęcia i udostępnia je za darmo. Poniżej 2 odcinki o tym temacie — dobre uzupełnienie, jeśli wolisz obejrzeć niż przeczytać.

Materiały Olimpijskiego Koła Informatycznego — kanał zewnętrzny. Kliknięcie odtwarza film tutaj, bez opuszczania strony.

Zadanie: Licznik jedynek

Zanim przejdziemy do mapy, rozgrzewka na tablicy — dobry punkt odniesienia, żeby zobaczyć, dlaczego przy trudniejszych ograniczeniach mapa staje się niezbędna.

📋 Treść zadania
Wejście
n — liczba elementów, a w drugiej linii a[0] a[1] ... a[n-1].
Wyjście
Liczba elementów tablicy równych 1.
Ograniczenia
n ≤ 10^6·0 ≤ a[i] ≤ 10^6
▶ Przykład
Wejście
7
1 2 5 1 5 2 2
Wyjście
2
licznik_jedynek.cpp
#include <iostream>
#include <vector>
using namespace std;

int main() {
    int suma = 0;
    int n;
    cin >> n;

    vector<int> lista(n);
    for (int i = 0; i < n; i++) {
        cin >> lista[i];
    }

    for (int i = 0; i < n; i++) {
        if (lista[i] == 1) {
            suma++;
        }
    }

    cout << "tyle jest jedynek: " << suma << endl;
}
▶ Pomysł
Wczytujemy całą tablicę do vector<int>, a potem przechodzimy po niej raz jeszcze i za każdym razem, gdy trafimy na 1, zwiększamy licznik suma o jeden.
▶ Wyjście programu (dla przykładu)
tyle jest jedynek: 2

Zadanie: Zliczanie

To samo zadanie co wyżej, tylko zamiast liczyć jedynki, liczymy ile razy wystąpiła każda wartość z tablicy. Ograniczenia na wartości a[i] decydują, jakiej struktury danych warto użyć — poniżej trzy warianty tego samego problemu.

📋 Treść zadania
Wejście
n — liczba elementów, a w drugiej linii a[0] a[1] ... a[n-1].
Wyjście
Dla każdej wartości, która wystąpiła w tablicy, wypisz ją razem z liczbą wystąpień.
Ograniczenia
Zależą od wariantu — patrz poniżej.

Wariant 1 — małe wartości

1 ≤ n ≤ 10^5  ·  0 ≤ a[i] ≤ 5
zliczanie_int.cpp
#include <iostream>
#include <vector>
using namespace std;

int main() {
    int zero = 0, jeden = 0, dwa = 0, trzy = 0, cztery = 0, piec = 0;
    int n;
    cin >> n;

    vector<int> lista(n);
    for (int i = 0; i < n; i++) cin >> lista[i];

    for (int e : lista) {
        if (e == 0) zero++;
        if (e == 1) jeden++;
        if (e == 2) dwa++;
        if (e == 3) trzy++;
        if (e == 4) cztery++;
        if (e == 5) piec++;
    }

    cout << zero   << endl;
    cout << jeden  << endl;
    cout << dwa   << endl;
    cout << trzy  << endl;
    cout << cztery << endl;
    cout << piec  << endl;
}
▶ Pomysł
Skoro wartości jest tylko 6 (0-5), nie trzeba żadnego kontenera — wystarczy sześć osobnych zmiennych int, po jednej na każdą wartość.
▶ Wyjście (dla 1 5 3 2 1 1 2)
0 3 2 1 0 1

Wariant 2 — średnie wartości

1 ≤ n ≤ 10^5  ·  0 ≤ a[i] ≤ 10^6
zliczanie_vector.cpp
#include <iostream>
#include <vector>
using namespace std;

int main() {
    vector<int> liczniki(1000001, 0); // indeks = wartość
    int n;
    cin >> n;

    vector<int> lista(n);
    for (int i = 0; i < n; i++) cin >> lista[i];

    for (int e : lista) liczniki[e]++;

    for (int i = 0; i < 1000001; i++) {
        if (liczniki[i] == 0) continue;
        cout << i << " -> " << liczniki[i] << endl;
    }
}
▶ Pomysł
10^6 osobnych zmiennych to za dużo, żeby je nazwać ręcznie, ale wciąż mało jak na indeks tablicy — vector o rozmiarze 1000001 mieści się bez problemu w pamięci (kilka MB).
▶ Wyjście (dla 1 5 3 2 1 1 2)
1 -> 3 2 -> 2 3 -> 1 5 -> 1

Wariant 3 — bardzo duże i ujemne wartości

1 ≤ n ≤ 10^5  ·  -10^18 ≤ a[i] ≤ 10^18
zliczanie_map.cpp
#include <iostream>
#include <vector>
#include <map>
using namespace std;

int main() {
    map<long long, long long> liczniki;
    int n;
    cin >> n;

    vector<long long> lista(n);
    for (int i = 0; i < n; i++) cin >> lista[i];

    for (long long e : lista) liczniki[e]++;

    for (pair<long long, long long> el : liczniki) {
        cout << el.first << " -> " << el.second << endl;
    }
}
▶ Pomysł
Przy zakresie do 10^18 (i wartościach ujemnych) nie da się zrobić tablicy indeksowanej wartością — mapa trzyma tylko te klucze, które faktycznie wystąpiły, i sama je sortuje. Użyto long long zamiast zwykłego long, bo na części platform long ma tylko 32 bity — za mało na 10^18.
▶ Wyjście (dla -1000000000000000000, 5, 1000000000000000000, 5, 1000000000000000000)
-1000000000000000000 -> 1 5 -> 2 1000000000000000000 -> 2
🚫
Dlaczego nie da się tego zrobić na vector?
Indeks tablicy czy vectora w C++ musi być liczbą nieujemną — to zawsze typ bez znaku (size_t). Zapis liczniki[-5] się nie skompiluje sensownie: -5 zostanie po cichu przekonwertowane na ogromną liczbę dodatnią (tzw. underflow) i program spróbuje sięgnąć daleko poza dostępną pamięć, co kończy się awarią. Mapa tego problemu nie ma — kluczem może być dowolna liczba, w tym ujemna, bo klucze nie są adresami w pamięci, tylko zwykłymi wartościami przechowywanymi w strukturze drzewa.
💾
Dlaczego rozmiar 10^18 to problem?
Żeby zaindeksować wartości z zakresu od -10^18 do 10^18 zwykłym vectorem (tak jak w wariancie 2), potrzeba by tablicy o długości rzędu 2×10^18 elementów. Nawet po 1 bajcie na element to ok. 2 eksabajty pamięci — o wiele więcej, niż ma jakikolwiek komputer (typowy limit pamięci w zadaniach to 256 MB). Mapa zużywa pamięć proporcjonalną tylko do liczby faktycznie wczytanych elementów (tu maks. n ≤ 10^5), a nie do rozpiętości możliwych wartości — dlatego ogromny zakres a[i] jej nie przeszkadza.

Czym jest mapa?

map przechowuje pary klucz → wartość. Zamiast szukać czegoś po numerze indeksu, jak w tablicy, szukamy po własnym kluczu, np. imię → wiek. Każdy klucz może wystąpić tylko raz, a elementy są zawsze automatycznie posortowane według klucza.

skladnia.cpp
#include <map>

map<typKlucza, typWartosci> nazwa;

// przykład:
map<string, int> wiekOsoby;

[], count, erase, iterowanie

Kilka operacji wystarczy, żeby swobodnie posługiwać się mapą — od dodawania wartości, przez sprawdzanie obecności klucza, po przeglądanie całej zawartości.

🔑

m[klucz] = wartość

Dodaje lub nadpisuje wartość pod danym kluczem. Odczyt m[klucz] dla nieistniejącego klucza automatycznie go dodaje!

🔍

count(klucz)

Bezpiecznie sprawdza, czy klucz istnieje, bez przypadkowego dodania go do mapy — w przeciwieństwie do [].

🗑️

erase(klucz)

Usuwa dany klucz razem z jego wartością z mapy. Po usunięciu rozmiar mapy zmniejsza się o jeden.

🔁

for (pair<K,V> p : m)

Przechodzi po wszystkich parach klucz-wartość, zawsze w kolejności posortowanej według klucza. Dostęp: p.first, p.second.

wiek_osoby.cpp
#include <iostream>
#include <map>
#include <string>
using namespace std;

int main() {
    map<string, int> wiekOsoby;
    wiekOsoby["Kacper"] = 20;
    wiekOsoby["Ania"] = 17;

    if (wiekOsoby.count("Ania") > 0)
        cout << "Ania jest w mapie";

    for (pair<string, int> os : wiekOsoby)
        cout << os.first << os.second;

    return 0;
}
▶ Wyjście programu
Ania jest w mapie Ania17Kacper20

count — czy klucz istnieje?

count(klucz) zwraca, ile razy dany klucz występuje w mapie. Ponieważ w map każdy klucz może wystąpić co najwyżej raz, wynik zawsze wynosi 0 (klucza nie ma) albo 1 (klucz istnieje) — nigdy nic pomiędzy ani nic więcej.

count.cpp
#include <iostream>
#include <map>
#include <string>
using namespace std;

int main() {
    map<string, int> oceny;
    oceny["Kacper"] = 5;
    oceny["Ania"] = 4;

    cout << oceny.count("Kacper") << endl; // klucz istnieje
    cout << oceny.count("Zosia")  << endl; // klucza nie ma

    if (oceny.count("Ania")) {
        cout << "Ania ma ocene: " << oceny["Ania"] << endl;
    }
}
▶ Wyjście programu
1 0 Ania ma ocene: 4
▶ Uwaga
count() zwraca int (0 albo 1), więc mozna go użyć wprost jako warunku w if — 0 zachowuje się jak false, a 1 jak true. To bezpieczniejszy sposób sprawdzania klucza niż m[klucz], bo count() nigdy nie dodaje nowego klucza do mapy.
🔢
Skąd w ogóle 0 albo 1, a nie więcej?
To wynika wprost z definicji map — jest to kontener o unikalnych kluczach, więc każdy klucz może się w niej pojawić najwyżej raz. Gdyby zamiast map użyć multimap (kontenera dopuszczającego powtarzające się klucze), count() mógłby zwrócić dowolną nieujemną liczbę — tyle, ile razy dany klucz faktycznie wystąpił.

Usuwanie elementów — erase

erase(klucz) usuwa z mapy dany klucz razem z jego wartością. Jeśli klucza nie ma w mapie, nic się nie dzieje — nie ma żadnego wyjątku ani błędu.

magazyn.cpp
#include <iostream>
#include <map>
#include <string>
using namespace std;

int main() {
    map<string, int> magazyn;
    magazyn["sruby"] = 120;
    magazyn["mlotki"] = 8;
    magazyn["gwozdzie"] = 500;

    cout << "przed usunieciem: " << magazyn.size() << endl;

    magazyn.erase("mlotki");

    cout << "po usunieciu: " << magazyn.size() << endl;

    if (magazyn.count("mlotki") == 0)
        cout << "mlotkow juz nie ma w magazynie" << endl;

    magazyn.erase("srubokrety"); // klucza nie ma - nic sie nie dzieje
}
▶ Wyjście programu
przed usunieciem: 3 po usunieciu: 2 mlotkow juz nie ma w magazynie
▶ Uwaga
Ostatnia linijka (erase na kluczu "srubokrety", którego nie ma) jest całkowicie bezpieczna — nie spowoduje żadnego błędu, po prostu nic nie usunie. size() maleje o 1 tylko wtedy, gdy klucz faktycznie istniał.

Przechodzenie przez mapę i wyświetlanie

Pętlę for (pair<K,V> el : mapa) można zastosować do wypisania całej zawartości mapy naraz. Elementy zawsze pojawiają się w kolejności rosnącej według klucza — nie trzeba nic sortować ręcznie.

Najłatwiej to sobie wyobrazić tak: mapa zachowuje się jak vector<pair<Klucz, Wartość>>, który jest zawsze posortowany według klucza. Pętla for po prostu idzie po tym "wektorze" od początku do końca, a każdy element el to jedna para — z kluczem pod el.first i wartością pod el.second.

Mentalny model: map<string, int> zwierzeta jako posortowany vector<pair<string, int>>
[0]
"kon" : 1
→
[1]
"kot" : 3
→
[2]
"pies" : 5
→
[3]
"waz" : 2
wyswietlanie_mapy.cpp
#include <iostream>
#include <map>
using namespace std;

int main() {
    map<char, int> mapa;
    mapa['A']++;
    mapa['B'] = 5;

    cout << mapa['A'] << endl;
    cout << mapa['A']+mapa['B'] << endl;

    cout << "wyswietlanie mapy: " << endl;
    for (pair<char, int> el : mapa) {
        cout << el.first << ' ' << el.second << endl;
    }
}
▶ Wyjście programu
1 6 wyswietlanie mapy: A 1 B 5
▶ Wersja z auto
for (auto el : mapa) { cout << el.first << ' ' << el.second << endl; } // dziala identycznie - // kompilator sam dobiera typ

Wszystko, co robi się z mapą

Mapa trzyma dane w drzewie, więc prawie każda operacja kosztuje O(log n) — dla miliona kluczy to około dwudziestu kroków. Poniżej wszystkie metody, które realnie się przydają, razem z kosztem.

MetodaCo robiJak szybko
m[k] = w Wstawia albo nadpisuje wartość pod kluczem. błyskawicznie
m[k] Odczyt — ale tworzy klucz, jeśli go nie było. błyskawicznie
m.at(k) Odczyt bez tworzenia. Zgłasza błąd, gdy klucza brak. błyskawicznie
m.count(k) Zwraca 1 albo 0. Bezpieczny test istnienia. błyskawicznie
m.insert({k, w}) Wstawia tylko wtedy, gdy klucza jeszcze nie ma. błyskawicznie
m.erase(k) Usuwa po kluczu. Bezpieczne, gdy klucza nie ma. błyskawicznie
m.size() / m.empty() Liczba par i test pustości. natychmiast
m.clear() Usuwa całą zawartość. zależy od rozmiaru
m.begin() / m.rbegin() Para z najmniejszym i największym kluczem. natychmiast
for (auto [k, w] : m) Przejście po wszystkich parach, rosnąco po kluczu. jedno przejście
unordered_map To samo, ale bez kolejności — za to szybciej. jeszcze szybciej

Drugi wiersz tabeli to najważniejsza pułapka mapy. Zwykły odczyt m[klucz] przy nieistniejącym kluczu tworzy go i wstawia wartość domyślną. Mapa po cichu rośnie, a warunek zwraca coś, czego nigdy tam nie było.

pulapka_nawiasow.cpp
#include <iostream>
#include <map>
#include <string>
using namespace std;

int main() {
    map<string, int> wiek;
    wiek["Ala"] = 16;

    cout << wiek.size() << "\n";        // 1

    // ZŁE: samo sprawdzenie tworzy klucz "Ola"
    if (wiek["Ola"] == 0)
        cout << "Oli nie ma\n";
    cout << wiek.size() << "\n";        // 2 - mapa urosła!

    // DOBRE: count nic nie tworzy
    if (wiek.count("Ela") == 0)
        cout << "Eli nie ma\n";
    cout << wiek.size() << "\n";        // nadal 2

    // DOBRE: find, gdy potrzebujesz też wartości
    auto it = wiek.find("Ala");
    if (it != wiek.end())
        cout << it->first << " ma " << it->second << " lat";

    return 0;
}
▶ Wyjście programu
1 Oli nie ma 2 Eli nie ma 2 Ala ma 16 lat

Zasada jest prosta: [] używaj tylko wtedy, gdy chcesz zapisać albo gdy domyślne zero jest ci na rękę (jak przy zliczaniu). Do samego sprawdzania bierz count, a gdy potrzebujesz też wartości — find.

Zostaje pytanie, czy w ogóle potrzebujesz mapy. Poniżej wszystkie sensowne alternatywy — ostatni wiersz bywa zaskoczeniem, ale przy kluczach będących małymi liczbami zwykła tablica bije mapę na głowę.

StrukturaCo trzymaKiedy wybrać
map Klucz → wartość, klucze posortowane rosnąco. Gdy potrzebujesz kolejności
unordered_map Klucz → wartość, bez żadnej kolejności. Gdy liczy się tylko szybkość
multimap Jeden klucz może mieć wiele wartości. Rzadko — lepszy map<K, vector<V>>
set Same klucze, bez wartości. Gdy pytasz tylko „czy to już było?”
tablica t[k] Klucz jako indeks tablicy. Gdy klucze to małe liczby, np. 0…106

Sprawdź się na zadaniach

Sześć zadań od najprostszego. W każdym kluczowe jest to samo pytanie: co jest kluczem, a co wartością? Gdy odpowiesz na nie dobrze, reszta to zwykle dwie linijki. Rozwiązania są schowane — najpierw spróbuj sam.

Łatwe Licznik słów
Wczytuj słowa aż do końca danych. Wypisz każde słowo wraz z liczbą jego wystąpień, alfabetycznie.
Jak to ugryźć: Jedna linijka robi całą robotę: licznik[slowo]++. Mapa sama utworzy klucz z wartością zero, gdy słowo pojawi się po raz pierwszy — i sama posortuje wynik alfabetycznie.
Pokaż rozwiązanie
licznik_slow.cpp
#include <iostream>
#include <map>
#include <string>
using namespace std;

int main() {
    map<string, int> licznik;
    string s;

    while (cin >> s) {
        licznik[s]++;            // tworzy klucz, jesli trzeba
    }

    for (auto [slowo, ile] : licznik) {
        cout << slowo << ": " << ile << "\n";
    }

    return 0;
}
Łatwe Książka telefoniczna
Wczytaj n par: nazwisko i numer telefonu. Potem wczytuj nazwiska i dla każdego wypisz numer albo BRAK, jeśli osoby nie ma w spisie.
Jak to ugryźć: Uwaga na pułapkę: m[nazwisko] dla nieistniejącego klucza utworzy go z pustą wartością. Do sprawdzania używaj count, a dopiero potem sięgaj po wartość.
Pokaż rozwiązanie
telefony.cpp
#include <iostream>
#include <map>
#include <string>
using namespace std;

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

    map<string, string> spis;

    for (int i = 0; i < n; i++) {
        string nazwisko, numer;
        cin >> nazwisko >> numer;
        spis[nazwisko] = numer;
    }

    string pytanie;
    while (cin >> pytanie) {
        if (spis.count(pytanie)) {
            cout << spis[pytanie] << "\n";
        } else {
            cout << "BRAK\n";
        }
    }

    return 0;
}
Łatwe Najczęstsza litera
Wczytaj linię tekstu i wypisz literę, która występuje w niej najczęściej, wraz z liczbą wystąpień. Spacje pomijaj.
Jak to ugryźć: Mapa char → int i pętla po znakach. Potem przejdź mapę i znajdź największą wartość — zwykły wzorzec rekordu. Przy remisie wygra litera wcześniejsza alfabetycznie, bo mapa jest posortowana.
Pokaż rozwiązanie
najczestsza_litera.cpp
#include <iostream>
#include <map>
#include <string>
using namespace std;

int main() {
    string linia;
    getline(cin, linia);

    map<char, int> licznik;

    for (char c : linia) {
        if (c != ' ') licznik[c]++;
    }

    char najlepsza = ' ';
    int ile = 0;

    for (auto [znak, liczba] : licznik) {
        if (liczba > ile) {
            ile = liczba;
            najlepsza = znak;
        }
    }

    cout << najlepsza << ": " << ile;
    return 0;
}
Średnie Sumy po kategoriach
Wczytuj pary: nazwa kategorii i kwota. Wypisz sumę kwot dla każdej kategorii, alfabetycznie, oraz kategorię o największej sumie.
Jak to ugryźć: suma[kategoria] += kwota — mapa zsumuje wszystko sama. Największą znajdziesz drugim przejściem, tym samym wzorcem rekordu. Na sumy weź long long.
Pokaż rozwiązanie
kategorie.cpp
#include <iostream>
#include <map>
#include <string>
using namespace std;

int main() {
    map<string, long long> suma;

    string kategoria;
    long long kwota;

    while (cin >> kategoria >> kwota) {
        suma[kategoria] += kwota;
    }

    string najwieksza;
    long long rekord = -1;

    for (auto [nazwa, s] : suma) {
        cout << nazwa << ": " << s << "\n";

        if (s > rekord) {
            rekord = s;
            najwieksza = nazwa;
        }
    }

    cout << "Najwieksza: " << najwieksza << " (" << rekord << ")";
    return 0;
}
Średnie Najczęstsze słowo
Wczytaj tekst i wypisz słowo, które występuje najczęściej. Przy remisie wypisz to wcześniejsze alfabetycznie.
Jak to ugryźć: Zliczanie mapą, a potem jedno przejście szukające maksimum. Remis rozwiąże się sam, jeśli użyjesz warunku > (a nie >=) — mapa przechodzi klucze alfabetycznie, więc pierwsze napotkane wygra.
Pokaż rozwiązanie
najczestsze.cpp
#include <iostream>
#include <map>
#include <string>
using namespace std;

int main() {
    map<string, int> licznik;
    string s;

    while (cin >> s) licznik[s]++;

    string najlepsze;
    int ile = 0;

    for (auto [slowo, liczba] : licznik) {
        if (liczba > ile) {      // > a nie >=
            ile = liczba;
            najlepsze = slowo;
        }
    }

    cout << najlepsze << " " << ile;
    return 0;
}
Trudne Para o zadanej sumie — z indeksami
Wczytaj n liczb i wartość k. Znajdź dwie liczby o sumie k i wypisz ich pozycje (numerowane od 1). Jeśli takiej pary nie ma — wypisz BRAK.
Jak to ugryźć: Zbiór odpowiedziałby tylko „jest albo nie ma”. Mapa pozwala zapamiętać, gdzie widziałeś każdą wartość: klucz to liczba, wartość to jej pozycja. Dla każdej nowej liczby x pytaj mapę o k - x.
Pokaż rozwiązanie
para_indeksy.cpp
#include <iostream>
#include <map>
using namespace std;

int main() {
    int n, k;
    cin >> n >> k;

    map<int, int> gdzie;        // wartosc -> pozycja

    for (int i = 1; i <= n; i++) {
        int x;
        cin >> x;

        if (gdzie.count(k - x)) {
            cout << gdzie[k - x] << " " << i;
            return 0;
        }

        gdzie[x] = i;           // zapamietujemy pozycje
    }

    cout << "BRAK";
    return 0;
}

Częste błędy i dobre praktyki

⚠️
m[klucz] dodaje klucz!
Samo odczytanie m[klucz] dla klucza, którego jeszcze nie ma, automatycznie go dodaje z wartością domyślną. Do samego sprawdzania używaj count().
🔁
Klucze się nie powtarzają
Przypisanie do istniejącego klucza nadpisuje wartość, a nie tworzy drugi taki sam klucz. Rozmiar mapy się wtedy nie zmienia.
📊
Zawsze posortowana
Elementy w map są automatycznie utrzymywane w kolejności rosnącej według klucza — nie trzeba nic dodatkowo sortować.
🧱
pair — first i second
Każdy element mapy to para pair<K,V>. Klucz odczytujemy przez .first, wartość przez .second.
🧮
Zastosowania
Mapa idealnie sprawdza się przy zliczaniu wystąpień, słownikach, systemach głosowania i grafach jako liście sąsiedztwa.
📦
Nagłówek <map>
Żeby korzystać z map, trzeba dołączyć nagłówek <map> — bez niego kompilator nie rozpozna tego typu.
🎥 Nie lubisz czytać?
Całość jest też w formie filmiku — obejrzyj poniżej.

Gotowy na więcej?

Dołącz do T-Olimpians i trenuj z doświadczonymi mentorami. Zbuduj bazę, która prowadzi do finałów OI.