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ć.
Zadanie: Licznik jedynek
Zanim przejdziemy do mapy, rozgrzewka na tablicy — dobry punkt odniesienia, żeby zobaczyć, dlaczego przy trudniejszych ograniczeniach mapa staje się niezbędna.
n — liczba elementów, a w drugiej linii a[0] a[1] ... a[n-1].1.n ≤ 10^6·0 ≤ a[i] ≤ 10^67 1 2 5 1 5 2 2
2
#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;
}
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.
n — liczba elementów, a w drugiej linii a[0] a[1] ... a[n-1].Wariant 1 — małe wartości
1 ≤ n ≤ 10^5 · 0 ≤ a[i] ≤ 5#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;
}
Wariant 2 — średnie wartości
1 ≤ n ≤ 10^5 · 0 ≤ a[i] ≤ 10^6#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;
}
}
Wariant 3 — bardzo duże i ujemne wartości
1 ≤ n ≤ 10^5 · -10^18 ≤ a[i] ≤ 10^18#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;
}
}
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.-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.
#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.
#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;
}
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.
#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;
}
}
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.
#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
}
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.
map<string, int> zwierzeta jako posortowany vector<pair<string, int>>#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;
}
}
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.
| Metoda | Co robi | Jak 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.
#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;
}
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ę.
| Struktura | Co trzyma | Kiedy 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.
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
#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;
}
n par: nazwisko i numer telefonu. Potem wczytuj nazwiska i dla każdego wypisz numer albo BRAK, jeśli osoby nie ma w spisie.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
#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;
}
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
#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;
}
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
#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;
}
> (a nie >=) — mapa przechodzi klucze alfabetycznie, więc pierwsze napotkane wygra.Pokaż rozwiązanie
#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;
}
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.x pytaj mapę o k - x.Pokaż rozwiązanie
#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;
}