PROGRAMOWANIE I ALGORYTMY

szkoła fraktal
Zapraszamy na lekcję otwartą wrzesień 2023

Mapy, tablice asocjacyjne


Mapa map na pierwszy rzut oka wygląda jak zwykła tablica. W gruncie rzeczy jest to tablica asocjacyjna (kontener), która przechowuje tylko te indeksy (klucze) oraz przypisane do nich wartości, które są nam potrzebne. Dodatkowo, indeksem może być nie tylko liczba całkowita dodatnia, ale także liczba rzeczywista, ciąg znaków, ogromne liczby typu long long, pary oraz różnego rodzaju struktury, w których zdefiniowano operator porównania. Aby używać mapy, musisz dodać bibliotekę #include <map>. Podsumowując, elementem mapy jest para (klucz, wartość). Elementy mapy porządkowane są po kluczu.

Tworzenie mapy

Tworząc mapę, musisz zadeklarować jakiego typu jest klucz (indeks) oraz przypisana do niego wartość.

map <typ klucza, typ wartości > nazwa_mapy;

Np.:

map < string, int> mapa;

Dodawanie elementów do mapy

Dodanie nowego elementu do mapy jest bardzo proste. Wystarczy, że podasz indeks w nawiasie [ ] oraz wartość i załatwione. Elementy dodawane są w czasie logarytmicznym i są porządkowane po kluczu.

map < string, int> mapa;
string indeks = "ala ma kota";
mapa[indeks] = 12;

Odwoływanie się do elementów mapy

Aby sprawdzić, jaka wartość znajduje się pod danym indeksem, należy użyć operatora [ ]— nawiasu kwadratowego, a wewnątrz niego należy wpisać wartość indeksu.

map < string, int> mapa;
mapa["algorytm"] = 22;
cout<<mapa["algorytm"]; //22

Wypisanie zawartości mapy

Aby wypisać elementy mapy możemy posłużyć się specjalną wersją pętli for

//algorytm.edu.pl
#include<bits/stdc++.h>
using namespace std;

int main()
{
	map <string, int> mapa;
	mapa["ala"] = 3;
	mapa["ola"] = 10;
	mapa["kinga"] = 100;
	
	//pobieraj kolejne elementy z mapy i zapisuj je w zmiennej "i"
	//auto — automatycznie dopasuj typ zmiennej "i"
	//elementy w mapie są porządkowane po kluczu
	for(auto i: mapa)
		cout<</*klucz*/i.first<<" => "<</*wartość*/i.second<<endl;
	
	return 0;
}

Uwaga! Po nadaniu indeksu, domyślnie wartość mapy jest zerowana.

Przydatne metody

Załóżmy, że stworzyliśmy mapę map<string, int> mapa; i wykonaliśmy wstępne czynności:

//algorytm.edu.pl
#include<bits/stdc++.h>
using namespace std;

int main()
{
	map <string, int> mapa;
	mapa["ala"] = 3;
	mapa["ola"] = 10;
	mapa["kinga"] = 100;
	........	
	return 0;
}
  • mapa.clear() — czyszczenie zawartości mapy
  • int cnt = mapa.count("ola") — zliczenie wystąpień klucza "ola"
  • if(mapa.empty()) ... — sprawdzenie, czy mapa jest pusta (zwrócenie true, jeśli jest pusta)
  • mapa.clear() — czyszczenie zawartości mapy
  • mapa.erase ("ala") — usunięcie elementu z mapy o kluczu "ala" (w czasie logarytmicznym)
  • int liczba_elementow = mapa.size() — zwrócenie liczby elementów mapy