Explorando a STL - Aula 6 - Map

Escrito por Lúcio Figueiredo e Anita Almeida

O map (ou mapa) é uma estrutura de dados da STL do C++ semelhante ao Set. A função do map é de guardar pares representados por uma chave e um valor. Ou seja, cada chave inserida será mapeada para um certo valor especificado. Como um exemplo, podemos possuir um map que recebe strings como chaves e inteiros como valores, associando, por exemplo, a diferentes nomes de pessoas as suas respectivas idades.

Declaração

Para declarar um map, é preciso usar a biblioteca <map>. Após isso, especificamos o tipo dos elementos usados como chave e o tipo dos valores que serão mapeados para cada chave.

	#include <iostream> // Biblioteca iostream necessária para funcionar
	#include <map> // Biblioteca do map
	using namespace std;
	int main()
	{
	map<string, int> mapa1; // Declaração de map mapa1 que possui strings como chaves e ints como valores
	map<int, double> mapa2; // Declaração de map mapa2 que possui doubles como chaves e ints como valores
	return 0;
	}

view raw map_codigo1.cpp hosted with by GitHub

Inserção de elementos

Há duas maneiras de se inserir um par {chave, valor} no map. A primeira utiliza uma ideia semelhante ao pair e a segunda uma ideia semelhante à atribuição de um valor a uma determinada posição de um vetor. Em ambas as formas, a complexidade da inserção é de $O(\log_{} N)$.

	#include <iostream> // Biblioteca iostream necessária para funcionar
	#include <map> // Biblioteca do map
	using namespace std;
	int main()
	{
	map<string, int> mapa1; // Declaração do map mapa1 que possui strings como chaves e ints como valores
	// 1º método - usamos o comando insert e inserimos o par {chave, valor}
	mapa1.insert(make_pair("Ana", 5));
	// 2º método - usamos a atribuição de valor como em vetores
	mapa1["Ana"] = 5;
	return 0;
	}

view raw map_codigo2.cpp hosted with by GitHub

Busca de elementos

Para saber se uma certa chave foi inserida no map, podemos usar o comando find. Caso a chave não tenha sido inserida, esta função retorna um ponteiro para o final do map, que pode ser acessado com o comando end. Novamente, a complexidade desta operação é de $O(\log_{} N)$.

	#include <iostream> // Biblioteca iostream necessária para funcionar
	#include <map> // Biblioteca do map
	using namespace std;
	int main()
	{
	map<string, int> mapa1; // Declaração do map mapa1 que possui strings como chaves e ints como valores
	mapa1["Lucas"] = 13; // Insiro a chave "Lucas" de valor 13
	if(mapa1.find("Lucas") == mapa1.end()) // Se a chave "Lucas" não foi inserida no mapa
	{
	printf("Chave não encontrada"); // Imprimo "Chave não encontrada"
	}
	else // Senão, imprimo o seu valor
	{
	printf("%d", mapa1["Lucas"]);
	}
	}

view raw map_codigo3.cpp hosted with by GitHub

Remoção de um elemento

Para remover uma chave do map, basta utilizar o comando erase e especificar a chave desejada. A complexidade de remover uma chave é $O(\log_{} N)$.

	#include <iostream> // Biblioteca iostream necessária para funcionar
	#include <map> // Biblioteca do map
	using namespace std;
	int main()
	{
	map<string, int> mapa1; // Declaração do map mapa1 que possui strings como chaves e ints como valores
	mapa1["Lucas"] = 13; // Insiro a chave "Lucas" de valor 13
	if(mapa1.find("Lucas") == mapa1.end()) // Se a chave "Lucas" não foi inserida no mapa
	{
	printf("Chave não encontrada\n"); // Imprimo "Chave não encontrada"
	}
	else // Senão, imprimo o seu valor
	{
	printf("%d\n", mapa1["Lucas"]);
	}
	mapa1.erase("Lucas"); // Removo a chave "Lucas" do mapa usando o comando erase
	if(mapa1.find("Lucas") == mapa1.end()) // Se a chave "Lucas" não foi inserida no mapa
	{
	printf("Chave não encontrada\n"); // Imprimo "Chave não encontrada"
	}
	else // Senão, imprimo o seu valor
	{
	printf("%d\n", mapa1["Lucas"]);
	}
	}

view raw map_codigo4.cpp hosted with by GitHub

Percorrer um map

Ainda é possível percorrer um map, iterando por todas as chaves existentes na estrutura. Para fazer isso, usaremos o mesmo processo para iterar um set: Usaremos um iterator que se localiza na posição inicial do map (obtido pelo comando begin) e irá navegar por todos os elementos no mapa até o seu fim (função end). Vale lembrar que os pares (chave, valor) presentes no map são mantidos de forma ordenada (por padrão, crescentemente) pelo mesmo comparador do tipo pair.

	#include <iostream> // Biblioteca iostream necessária para funcionar
	#include <map> // Biblioteca do map
	using namespace std;
	int main()
	{
	map<string, int> mapa1; // Declaração do map mapa1 que possui strings como chaves e ints como valores
	mapa1["Lucas"] = 13; // Insiro a chave "Lucas" de valor 13
	mapa1["Ana"] = 7; // Insiro a chave "Ana" de valor 7
	mapa1["Thiago"] = 20; // Insiro a chave "Thiago" de valor 20
	map<string, int>::iterator it;
	for(it=mapa1.begin(); it!=mapa1.end(); it++) // O iterator it irá percorrer o map do seu ínicio ao fim
	{
	// O iterator it será um par de dois valores:
	printf("Chave: %d\n", (*it).first); // O seu valor first será a chave na posição atual do map
	printf("Valor: %d\n", (*it).second); // O seu valor second será o valor mapeado à chave
	}
	}

view raw map_codigo5.cpp hosted with by GitHub

Lista completa de funções

O map possui outras funções úteis que são muito utilizadas. Para conferí-las, basta acessar o link da referência do C++.

Problemas para praticar

Problema 1 - Lecture

Problema 2 - Inscrições

Problema 3 - Times