Breve introdução à classe genérica std::map

Sumário

1  Introdução

std::map é uma classe genérica do tipo contentor associativo ordenado.

Vejamos,

classe genérica podem ser definidos map de vários tipos (tal como já tinha sido observado com a utilização das classes vector e list, por exemplo), ou seja, é genérica;
contentor permite guardar vários itens (neste caso, pares (chave, valor));
associativo estabelece uma relação entre dois tipos (um par, portanto), em que o primeiro elemento do par é a chave e o segundo é o valor correspondente;
ordenado existe uma relação de ordem no conjunto dos valores da chave.

Para utilizar a classe genérica map, deverá acrescentar usar a seguinte directiva de inclusão:

#include <map>

No texto que se segue assume-se que se usou a directiva de utilização

using namespace std;

pelo que se omite o prefixo std::.

A classe genérica map deve ser parametrizada com os tipos dos elementos dos pares que irá guardar.  Por exemplo, map<string, unsigned> é uma classe de mapa (diz-se uma instanciação da classe genérica map) cujos itens são pares (string, unsigned).  Assim, para definir um mapa m cujos itens são pares do tipo (Chave, Valor), usa-se a seguinte instrução:

map<Chave, Valor> m;

Podem usar-se mapas para criar estruturas de dados mais complexas.  Por exemplo:

map<int, map<int, double> > m;

define um mapa m que associa a chaves do tipo int valores do tipo map<int, double>, que por sua vez associa a chaves do tipo int valores do tipo double.

Atenção:  Deve sempre existir um espaço entre o primeiro > e o segundo > em qualquer definição deste tipo.

2  Operações

Listam-se em seguida algumas das operações mais importantes das classes map<Chave, Valor> (instanciadas a partir da classe genérica map).

2.1  Acesso e alteração através do operador map<Chave, Valor>::operator[]

// Devolve por referência o valor associado à chave c.
Valor& map<Chave, Valor>::operator[](Chave const& c);

map<string, unsigned> telefones; // Define um mapa vazio.
telefones["João"] = 212121212;   // Acrescenta ao mapa o par (João, 212121212).
telefones["Joana"] = 961234567;  // Acrescenta ao mapa o par (Joana, 961234567).
telefones["João"] = 917654321;   // Substitui no mapa o par (João, 212121212) por 
                                 // (João, 917654321).

cout << telefones["Joana"] << endl;

// Aparece "961234567" no ecrã.

Quando o acesso se faz através de uma chave que não consta ainda no mapa, é inserido automaticamente um par (chave, valor) com a chave dada e com o valor por omissão do valor:

cout << telefones["Felizberto"] << endl;

// Aparece "0" no ecrã.

2.2  Pares (chave, valor)

Repare-se que falamos sempre de pares, mas nunca "vimos" um. No entanto, é possível trabalhar directamente com pares.  Um par pode ser definido da seguinte forma:

string nome("Maria");
pair<string, unsigned> telefone(nome, 931234567);
// Ou pair<string, unsigned> telefone(make_pair(nome, 931234567));

Para aceder à chave (primeiro elemento do par), deve usar-se a seguinte instrução:

cout << "Chave: " << telefone.first << endl; // Aparece no ecrã "Maria".

Para aceder ao valor (segundo elemento do par), deve usar-se a seguinte instrução:

cout << "Valor: " << telefone.second << endl; // Aparece no ecrã "931234567".

2.3  Inserção com a operação map<Chave, Valor>::insert()

Para inserir pares (chave, valor), pode-se usar os pares com a classe genérica map como se segue:

/* Devolve um par (map<Chave, Valor>::iterator, bool), em que o
   iterador referencia a posição onde o par par foi inserido e o bool é true, caso a
   inserção tenha sido bem sucedida; caso já exista um elemento com chave par.first,
   o iterador referencia a posição desse elemento e o bool tem o valor false. */
pair<map<Chave, Valor>::iterator, bool> map<Chave, Valor>::
    insert(pair<Chave const, Valor> const& par);

Exemplos:

pair<map<string, unsigned>::iterator, bool> resultado =
    telefones.insert(telefone);

if(not resultado.second)
    cout << "não ";
cout << "inseri" << endl;

// Aparece "inseri" no ecrã

resultado = telefones.insert(make_pair(nome, 217654321));

if(not p.second)
    cout << "não ";
cout << "inseri" << endl;

// Aparece "não inseri" no ecrã, pois a inserção falha se existe já um par com a 
// mesma chave.

2.4  Procura de pares com map<Chave, Valor>::find() e map<Chave, Valor>::count()

Para saber se um par existe e para o procurar, podem-se usar as seguintes operações:

/* Devolve o número de pares cuja chave é chave. No caso dos mapas devolve
   sempre 0 ou 1.  Há uma outra classe genérica, multimap, que permite chaves
   repetidas, para a qual esta operação pode devolver valores superiores a 1. */
map<Chave, Valor>::size_type map<Chave, Valor>::count(Chave const& chave);

// Devolve um iterador constante para o par cuja chave é chave.  Caso a chave não
   exista devolve o iterador para o item fictício final:
map<Chave, Valor>::const_iterator map<Chave, Valor>::find(Chave const& c) const;

map<Chave, Valor>::iterator map<Chave, Valor>::find(Chave const& c);

Exemplos:

string nome("Maria");

if(telefones.count(nome) != 0)
    cout << nome << " ..... " << telefones.find("Maria")->second << endl;
else
    cout << nome << " ..... (não encontrado)" << endl;

// ou

if(telefones.find(nome) != telefones.end())
    cout << nome << " é " << telefones.find("Maria")->second << endl;
else
    cout << nome << " não encontrado" << endl;

2.5  Remoção de pares com map<Chave, Valor>::erase()

Para remover um par de um mapa pode-se usar a seguinte operação:

/* Remove o par com a chave chave, devolvendo o número de pares removido
   (0 ou 1).  Infelizmente é uma operação dois-em-um. */
map<Chave, Valor>::size_type map<Chave, Valor>::erase(const Chave& chave);

Exemplo:

if(telefones.erase("João") == 0)
    cout << "O joão não constava da lista..." << endl;

cout << telefones.count("João") << endl;

// Aparece "0" no ecrã.

2.6  Percorrendo mapas com iteradores

Como percorrer todos os itens de um map?  Tal como com na classe genérica vector, podemos usar iteradores para percorrer os itens de um mapa.  O ciclo abaixo percorre todos os itens do mapa map<string, unsigned> telefones por ordem crescente da chave:

typedef map<string, unsigned>::const_iterator Iterador;

for(Iterador i = telefones.begin(); i != telefones.end(); ++i)
    cout << i->first << ' ' << i->second << endl;

Atenção:  Como foi referido no início, tem de existir uma relação de ordem no conjunto dos valores da chave, pelo que o operador < deve existir para o tipo da chave.