Map

Z RNO-Wiki

Mapa (ang. map)

Mapa w C++ to struktura realizująca tablicę asocjacyjną. Można to rozumieć jak tablicę indeksowaną byle czym. Zamieszczam program, wykorzystujący mapę - tablicę indeksowaną int'ami, w której będziemy przechowywać int'y.

Poniważ mapa jest bardzo związana ze zbiorem set, więc przeczytaj najpierw notatki o set'cie. Właściwie to mapa jest zbiorem par.

Dla mapy dostępne są następujące instrukcje (wiele z nich jest podobnych do instrukcji dla set'a)

  • clear() - czyści całą mapę (sprawa, że będzie pusta)
  • size() - zwraca liczbę elementów w mapie
  • erase(x) -
  • find(x) -
  • lower_bound(x) -
  • upper_bound(x) -
  • .. więcej na stronie [1]

W C++ mapę można uzyskać w następujący sposób:

 #include<map>

i mamy już typ z wzorcem (ang. templatem)

 map<key_type, value_type> A; // A jest mapą indeksowaną obiektami typu 'key_type' (to właśnie dla nich jest potrzebny operator mniejszości, jak dla set'a), której wartości są typu 'value_type'

Na mapę indeksowaną int'ami, której wartości są int'ami otrzymujemy następująco:

 map<int, int> T;

Piękne jest to, że możemy zrobić

 T[2000000000] = 10;

Widzimy, że obsługa mapy została zrobiona tak, aby wyglądała ona jak zwykła tablica. Nie jest to jednak zwykła tablica, bo aby dostać się do komórki o numerze 2000000000 nie potrzebujemy wszystkich poprzednich. Niestety nie ma nic za darmo. Dostęp do komórki T[1000] kosztuje <math>O(\log(n))</math>, gdzie <math>n</math> to aktualna liczba elementów mapy.

Uwaga: samo odwołanie się do wartości komórki (niekoniecznie przypisanie jej wartości) nadaje jej wartość domyślną jeśli takiej nie było. Na przykład poniższa intrukcja wypisze 'TAK' nawet jeśli T[5] nie jest określone w mapie:

 if (T[5] < 9) printf("TAK");

Aby sprawdzić, czy istnieje wartość T[100] należy użyć instrukcji count(100):

 if ( T.count(100) ) printf("Istnieje wartosc T[100] i wynosi ona %d\n",  T[100]);

Iteratory

Tak jak każdy kontener STL'owy, mapa ma iteratory. W tym celu mamy typ

 map<int,int>::iterator iter;

Teraz zmienna o nazwie 'iter' jest iteratorem w mapie liczb całkowitych indeksowanej liczbami całkowitymi.

Wspomniana wcześniej funkcja find zwraca iterator. Załóżmy, że nie jest on równy iteratorowi T.end(). Możma myśleć, że iterator to wskaźnik na parę, dla której first to wartość klucza, a second to wartość T[klucz], czyli wartość wartości :-)

 iter = T.find(2000000000);
 assert( iter->first == 2000000000 );
 assert( iter->second == 10 ); // bo T[2000000000] == 10

Teraz jasne jest jak, przeglądać całą zawartość mapy np. od początku do końca.

 for ( iter = T.begin(); iter != T.end(); iter++ )
 {
    printf("T[%d]=%d\n", iter->first, (*iter).second); // można pisać iter->first lub (*iter).first
    iter++;
 }

Przykład

Najwięcej nauczysz się, gdy dokładnie przeanalizujesz poniższy kod w C++. Skopiuj go sobie i skompiluj.

#include <cstdio>
#include <map>  // aby móc uzywać mapy

using namespace std;

int main(void)
{
	map<int, int> T; // można myśleć, że to jest tablica intów, ale z dziurami :-)
	
	T[100] = 5;
	T[1000000000] = 90; // można dostać się do komórki nr 10^9 ; super, co nie?
	
	// UWAGA : Dostęp np. do T[100] kosztuje : O( log(n) ) , gdzie n to aktualna liczba elementów w mapie
	
	// --------------------------
	
	// Aby sprawdzić, czy istnieje wartość T[45], wykonujemy instrukcję find(45)
	if ( !T.count(45) )  printf("Nie istnieje wartosc T[45].\n");
	if ( T.count(100) ) printf("T[100] = %d\n", T[100]);
	
	
	// --------------------------
	
	if ( !T.count(5) ) printf("Nie istnieje wartosc T[5].\n");
	
	// UWAGA : ponizszy if sprawi, ze T[5] bedzie mialo wartosc 0
	if (T[5] < 2) printf("Pierwsze odwolanie sie do T[5] sprawia, ze ma nieokreslona wartosc. Tutaj wynosi ona :\n");
	
	if (  T.count(5) ) printf("T[5] = %d\n", T[5]);
	
	// --------------------------
		
	T[400]  = 1;
	T[1]    = 400;
	T[2000] = 19;
	
	map<int, int>::iterator I; // I - jest iteratorem mapy	
	
	I = T.find(2000); // O( log(n) )
	// *I <-- dostęp w czasie stałym, w przeciwieństwie do T[2000], który działa w czasie O(log(n))
	if ( I!=T.end() ) printf("T[2000]=%d\n", (*I).second );
	
	I++; // teraz I wskazuje na następny element mapy, ale JAKI ???
	int klucz   = (*I).first;
	int wartosc = I->second; //  to samo, co  (*I).second
	
	printf("T[%d] = %d\n", klucz, wartosc   ); // T[
	printf("T[%d] = %d\n", klucz, I->second ); // to samo
	
	// Usuwanie
	T.erase(190);  // to wywołanie zwraca 0
	T.erase(2000); // to wywołanie zwraca 1 
	
	
	printf("Zawartosc mapy:\n");
	// Przeglądanie całej mapy : O( n log(n) )
	for( I=T.begin();  I!=T.end(); I++)
	{
		printf("T[%d]=%d\n", I->first, I->second);
	}
	printf("---------------\n");
	
	
	// Usuwanie za pomocą iteratora
	I = T.find(1000000000);
	T.erase(I);
}
Osobiste