Sztuczki w c++ cz.2 - mapy - Blog CYBERCRATE.PL

BLOG.CYBERCRATE.PL

Kreatywnie o technologii

Sztuczki w C++ #2

Przydatne tricki i ułatwienia - mapy

Drugi wpis z serii ciekawych tricków, poświęcę na szybką dyskusję o mapach. Na początek warto by powiedzieć, czym owe mapy są. Mapa jest typem kontenera/kolekcji, a prościej mówiąc jest magazynem danych. Standardowa biblioteka języka c++ udostępnia nam wiele takich narzędzi (należą do nich np wektory, listy, mapy, zbiory, oraz wiele innych). Dociekliwy czytelnik zadaje sobie teraz najpewniej pytanie, po co nam tyle aż metod na przechowywanie danych, skoro mamy zwyczajne tablice. Odpowiedź jest dosyć prosta – każdy z tych kontenerów, charakteryzuje się specyficznymi cechami, któe okazują się przydatne w konkretnych zastosowaniach. Np. dla wektora nie musimy znać początkowej wielkości – kontener dopasuje się do ilości danych jaką podamy; zbiory umożliwiają bardzo szybkie sprawdzanie czy dany element występował w zbiorze, natomiast listy umożliwiają bardzo szybkie operacje edycji.

Zanim przeczytasz: Ten artykuł został napisany głównie z myślą o osobach przygotowujących się do egzaminu maturalnego, zawodowego, lub innego wymagającego nieznacznej znajomości c++. Z tego względu pomijam wiele treści istotnych np na konkursach takich jak złożoność obliczeniowa. Koncentruję się jedynie na ułatwieniach, bez szerszego omawiania mechanizmów za nimi stojących. Materiał opisujący mapy i sztuczki z nimi związane w ujęciu bardziej profesjonalnym zostanie opublikowany w niedalekiej przyszłości.

Czym jest mapa?

Przechodząc do sedna, mapa jest kontenerem który przechowuje dwie wartości – klucz i wartość. Za każdym razem gdy chcemy uzyskać wartość, lub ją edytować, podajemy mapie klucz, pod jakim powinna szukać tego elementu. Co może być kluczem? W zasadzie nie znalazłem żadnych specjalnych ograniczeń co do typu (ważne jedynie, aby dało się te obiekty porównywać z użyciem funkcji compare). A teraz bardziej obrazowo – powiedzmy, że masz bazę numerów telefonów i chcesz policzyć ile minut trwały w sumie połączenia z każdym z numerów z bazy połączeń. W takim przypadku, możemy sobie utworzyć właśnie mapę, gdzie kluczem będzie numer telefonu – string, a wartością będzie ilość minut połączeń.

#include <map>  // W tym pliku mamy definicję mapy
using namespace std;    // Normalnie pisalibyśmy std::map<...> ale dzięki tej linijce pomijamy std::
//...
int main(){
    
    string[1000] numery;
    int[1000] czas;
    //para numery[i], czas[i] opisuje i-tą rozmowę
    
    // W ostrych nawiasach podaję typy, najpierw klucza, a następnie wartości które będzimy przechowywać
    map<string,int> sumy;
    for(int i = 0; i<1000; i++)
        // Do elementów mapy odwołuję się tak samo jak do elementów tablicy, tylko zamiast indeksu używam klucza
        sumy[numery[i]]+=czas[i];
    //...
}

Kod powyżej w zaledwie 3 linijkach rozwiązuje nam całe zadanie, korzystając z jednej ciekawej cechy mapy – int’y zawsze są inicjalizowane jako zera. Czyli na ludzki – kiedy dodamy coś do wartości opisanej przez nie istniejący jeszcze numer telefonu, to mapa nie znając tej wartości, uzna że jest to zero.

Jak używać mapy?

Zacznijmy od pliku nagłówkowego, jak wiemy , aby w c++ skorzystać z jakiejś funkcjonalności biblioteki standardowej, której częścią jest mapa, musimy użyć #include, oraz w ostrym nawiasie podać plik do którego się odwołujemy. A po polsku – żeby użyć mapy musimy powiedzieć kompilatorowi gdzie jej szukać.

#include <map>

Kolejną sprawą jest przestrzeń nazw. Chodzi tutaj o to, że deweloperzy biblioteki standardowej opakowali ją w tak zwaną przestrzeń nazw. Zrobili to dlatego, że biblioteka jest duża i zużywa bardzo dużo nazw funkcji, klas itd. Aby nie mylić tych z biblioteki z naszymi, te biblioteczne znajdują się w takim jakby kontenerze. Aby odwołać się do czegoś co w nim jest piszemy std::nazwa_funcki_z_kontenera. Możemy pamiętać o tym i w przypadku mapy zawsze pisać std::map<…> albo też użyć dyrektywy która powie kompilatorowi, że jeśli sami nie powiemy mu co to map, to ma szukać w danym kontenerze. To właśnie robi dyrektywa using namespace.

using namespace std;

Mapę przechowujemy w zmiennej. Aby z niej korzystać musimy jednak najpierw określić jej typ. To nie jest takie proste jak w przypadku zwyczajnych tablic, ale do przełknięcia. Najpierw podajemy typ map, tylko że on potrzebuje dwóch parametrów – typu danych które będą kluczem oraz typu danych które będą wartościami. Wyobraźmy sobie, że każdy element mapy jest słoikiem, teraz typ klucza to typ danych, który znajdzie się na etykiecie słoika, a typ wartości to typ danych, które włożymy do tego słoika. Deklarujemy to w następujący sposób:

map<TYP_KLUCZA, TYP_WARTOŚCI> NAZWA_ZMIENNEJ;

Czyli dla przykładu, chcąc zadeklarować mapę gdzie kluczami są int’y, a wartościami dane typu string, zrobimy to tak jak poniżej:

map<int,string> jakas_mapa;

Mając zadeklarowaną mapę, trzeba umieć dostać się do jej elementów. Robimy to podobnie jak w przypadku tablicy, tylko, że teraz zamiast numeru komórki, używamy wartości klucza

map<string,int> inna_mapa;

inna_mapa["jakis_klucz"] = 1;

inna_mapa["wyraz"] = 10;

cout<<inna_mapa["wyraz"]; // wypisuje 10
cout<<inna_mapa["jakis_klucz"]; // wypisuje 1

Teraz już wiesz jak korzystać z mapy. Można ładnie powiedzieć, że mapa jest klasą realizującą funkcję mapowania elementów będących kluczami do wartości (tak wpadłem na to waśnie teraz), ale my już wiemy jak ona działa i rozumiemy ją troszkę bardziej niż wyjaśnia to zdanie 😉

Sztuczki z mapami w c++

Po wprowadzeniu, teraz czas na rzeczy najciekawsze, czyli sztuczki c++ z mapami. Sztuczek będzie kilka, szczególnie pomocnych w momentach kiedy czasu jest niewiele, a potrzeba go jak najwięcej. Z pewnością użyjesz tych sztuczek na maturze, lub egzaminie zawodowym.

Przejście po całej mapie

Sztuczka, przydatna, do pokazania wszystkich elementów w mapie, gdy nie wiemy jakie są klucze, których używaliśmy. Można to zrobić na kilka sposobów. Zerknijmy na przykłady

map<string, int> mapa;

for(auto para : mapa)
    cout<<"klucz: "<<para.first<<"wartość: "<<para.second<<endl;

map<string, int> mapa;

for(auto m_iterator = mapa.begin(); m_iterator!= m.end(); m_iterator++ )
    cout<<"klucz: "<<m_iterator->first<<"wartość: "<<m_iterator->second<<endl;

map<string, int> mapa;

map<string, int>::iterator it = mapa.begin();

while(it != mapa.end())
    cout<<"klucz: "<<it->first<<"wartość: "<<it->second<<endl;

Istnieje jeszcze kilka sposobów, takich jak np. pętla for_each z std, ale aby nie zaciemniać, pozostańmy przy tych trzech pomysłach. Na okazje takie jak egzaminy, serdecznie polecam sposób numer 1 – najkrótszy.

Nieistniejący element

Warto przyjrzeć się także temu co dzieje się gdy odwołamy się do nie istniejącego elementu. Powiedzmy, że mamy kod taki jak poniżej

map<string, int> mapa;

cout<<mapa["a"];

Taki kawałek kodu spowoduje wypisanie 0 na standardowe wyjście. Dlaczego? Otóż mapy gdy inicjalizują typy wbudowane, zawsze ustawiają je na zero. Ten detal jest bardzo rzydatną sztuczką do realizacji zadań w c++.

Czyszczenie mapy

Często może być tak, że po jakichś operacjach na danych będziemy chcieli mapę przywrócić do stanu początkowego. Tutaj również mamy bardzo proste rozwiązanie

map<string, int> mapa;
//...
mapa.clear(); 
//mapa jest pusta

Sprawdzenie czy klucz istnieje w mapie

Ciekawym problemem jest sprawdzanie czy dany element wystąpił już w mapie. Można to zrobić na kilka sposobów, najprostszy, korzystając ze sztuczki prezentowanej powyżej, można iść po całej mapie i porównywać, ale mamy lepsze sposoby:

map<string, int> mapa;

if( mapa.find("jakis klucz") != mapa.end()){
    // "jakis klucz" jest w mapie
}

Ewentualnie, warto zauważyć, że jeśli ilość wystąpień jest większa od zera to element także występuje. A tak to zastosujemy:

map<string, int> mapa;

if( mapa.count("jakis klucz") > 0){
    // "jakis klucz" jest w mapie
}

Przykładowe zadanie

Napisz program, który policzy wystąpienia słów składających się ze znaków ASCII. Na wejściu otrzymujesz najpierw liczbę słów – n, gdzie 1<n<1000000, po czym w każdej linii podane jest i-te z n słów. Na wyjściu wypisz w osobnych liniach, dla każdego słowa, to słowo oaz ilość jego wystąpień.

Na pierwszy rzut oka, bez mapy, to zadanie wydaje się być nawet trudne, bo nie wiemy jakie te słowa będą się pojawiać, tak aby je jakoś ładnie tablicować. Tutaj jednak z pomocą przychodzi nam mapa.

#include <iostream>
#include <map>

using namespace std;

int main(){
    
    int n;
    
    cin>>n;
    
    map<string,int> slowa;
    
    while(n--){
        string slowo;
        cin>>slowo;
        slowa[slowo]+=1;
    }
    
    for(auto opis : slowa)
        cout<<opis.first<<" "<<opis.second<<endl;
    
    return 0;
}

Przyglądając się temu kawałkowi kodu, można bardzo łatwo zauważyć, jak bardzo mapa ułatwiła to zadanie, a w dodatku, zrobiła to dosyć szybko, bo w czasie logarytmicznym. Taki zapis, na egzaminie maturalnym może oszczędzić sporo czasu. Samodzielne konstruowanie tablic zapamiętujących słowa i ich wystąpienia, mogłoby kosztować sporo czasu, który jest raczej cennym zasobem na egzaminach. Tutaj całość mechanizmu zliczania jest już wykonana za nas, my musimy jedynie uruchomić odpowiednie procedury.

Dlaczego mapy

W zasadzie, teraz to sprawa jest raczej jasna. Mapa dostarcza Ci bardzo wielu gotowych funkcjonalności. Użycie ich pozwala zwyczajnie zaoszczędzić czas, który na egzaminach jest dość cenny. Należy też pamiętać, że sposób zapisu danych w mapie pozwala na względnie szybkie operacje przeszukania i zapisu – mają dobrą złożoność obliczeniową.