Map heterogêneo
Soluções simples quase sempre são as melhores
Outro dia estava com um problema onde precisa de um map que pudesse ser indexado por mais de um tipo de dado diferente. Chamei isso de map heterogêneo.
Pra quem não sabe, a template map da stl recebe dois tipos de dados e faz um dicionário. A hash_map faz a mesma coisa, porém mais rápido – mas o meu principal problema não era velocidade.
Exemplo de uso da map em C++
#include <iostream>
#include <map>
using namespace std;
int main(int argc, char *argv[])
{
map<string,int> dic;
dic["abacate"] = 3;
dic["maçã"] = 2;
cout << dic["abacate"] << endl;
cout << dic["maçã"] << endl;
cout << dic["banana"] << endl;
return 0;
}
(Gostei dessa formatação acima!)
O caso é que o tipo do índice do map tem de ser um só, e eu queria misturar int, double, char* e string. Lógico que poderia usar quatro maps diferentes, mas isso significaria passar quatro parâmetros a mais para várias funções. Antes de partir pra fazer uma classe com quatro maps diferentes (ou mais, veio logo essa dúvida!) e sobrecarregar o operador [], me ocorreu a seguinte idéia: e se um campo membro da classe pudesse ser template? Bom, isso não funciona – apenas métodos podem ser templates. Mas consegui um workaround que, se não é a coisa mais linda nem eficiente do mundo, resolveu bem o problema com um mínimo de esforço.
Um método pode ser template, e um método pode ter uma variável local do tipo do parâmetro da template. O problema é que uma variável local morre quando se sai do método. Mas e se essa variável fosse estática? Nesse caso surgiria outro problema – teria apenas uma instância da variável para todos os objetos da classe. O código abaixo ilustra isso.
Versão 0.1 da solução para map heterogêneo
#include <iostream>
#include <map>
using namespace std;
template <class T>
struct Map {
template <class I>
int& operator [] ( I i ) {
static map<I,int> m;
return m[i];
}
};
int main(int argc, char *argv[])
{
Map<int> dic, outroDic;
dic["abacate"] = 3;
dic["maçã"] = 2;
dic[0] = 1;
dic[0.0] = 5;
cout << dic["abacate"] << endl;
cout << outroDic["maçã"] << endl;
cout << dic["banana"] << endl;
cout << dic[0] << endl;
cout << dic[0.0] << endl;
return 0;
}
Saída:
3 2 0 1 5
Na linha 26, embora esteja usando a variável outroDic, o resultado não foi zero: as duas variáveis, dic e outroDic, copartilham o mesmo map, pois ele é estático. Daí veio a seguinte idéia: e se tivesse um map para o próprio objeto, ou seja, this? Bingo! resolvido o problema (já disse, é apenas uma solução simples – para ser eficiente teria de usar hash_map, e para ser elegante… bem, aí é outra estória…).
Versão 0.2 da solução para map heterogêneo
#include <iostream>
#include <map>
using namespace std;
template <class T>
struct Map {
template <class I>
int& operator [] ( I i ) {
static map<Map*, map<I,int> > m;
return m[this][i];
}
};
int main(int argc, char *argv[])
{
Map<int> dic, outroDic;
dic["abacate"] = 3;
dic["maçã"] = 2;
dic[0] = 1;
dic[0.0] = 5;
cout << dic["abacate"] << endl;
cout << outroDic["maçã"] << endl;
cout << dic["banana"] << endl;
cout << dic[0] << endl;
cout << dic[0.0] << endl;
return 0;
}
Saída:
3 0 0 1 5
Dessa vez a linha 26 corretamente produziu zero como saída, pois o dado foi armazenado associado ao ponteiro this, ou seja, ao próprio objeto. O que me deixou surpreso e satisfeito foi realmente a simplicidade da solução – apenas 6 linhas de código. E muito fácil de adaptar para hash_map para não ficar tão ineficiente…
Resolvi o meu problema imediato. Mas é a versão 0.2 ainda porque não tem iteradores… não parei ainda para pensar em uma forma de fazer um iterador único para cada variável, na verdade me ocorreu que somente seria possível ter um iterador para cada tipo de índice por causa do campo first. Uma pena… mas pelo menos para o meu problema o código acima já serve.
E para quem for mais atento, falta um destrutor para remover da variável estática m (linha 10) os Maps locais quando eles forem destruídos… é, talvez versão 0.2–
“Veni, vidi, vici”
Ótima solução! E bem criativa!
Porém, imagino que você já deva ter imaginado no problema que é confiar no ponteiro this. Não que seja comum a coincidência de um outro objeto ocupar o mesmo endereço de um objeto antigo, mas é possível. No exemplo abaixo eu forcei a situação:
int main(int argc, char *argv[])
{
Map *dic = new Map; // nosso primeiro dic
(*dic)["abacate"] = 3;
(*dic)["maçã"] = 2;
(*dic)[0] = 1;
(*dic)[0.0] = 5;
// imprime os valores que defini anteriormente
cout << (*dic)["abacate"] << endl;
cout << (*dic)["banana"] << endl;
cout << (*dic)[0] << endl;
cout << (*dic)[0.0] << endl;
delete dic; // apagamos o primeiro dic…
dic = new Map; //… e criamos mais um!
// teoricamente os valores abaixo seriam todos zero
cout << (*dic)["abacate"] << endl;
cout << (*dic)["banana"] << endl;
cout << (*dic)[0] << endl;
cout << (*dic)[0.0] << endl;
delete dic;
return 0;
}
Note que a saída se repete para os dois objetos, porque o this é o mesmo. Isso pode dar alguns bugs bem interessantes de ser resolvidos em código de produção
[]s
Pois é, ficou faltando fazer um destrutor para remover o sujeito.
[]s
Muito interessante tua implementação.
Veja esta outra : http://code.axter.com/HeterogeneousContainer3.cpp
Tenho preferência por uso de STL, facilita muito, sem precisar reinventar a roda. Mas para casos onde haja necessidade de acessos compartilhados (multi-thread) tem-se de implementar controle de acesso visto que os containers não são thread-safe.
Vai ai uma sugestão : criar uma classe/template para container (map ou hash_map, o que mais uso) que permita acessos concorrentes.
Uma situação comum para mim é esta :
- uma thread está fazendo acessos de leitura no container com seu iterator;
- uma segunda thread faz leituras e eventualmente remove ítens do container;
Se não houver um controle eficiente que garanta a validade do iterator, este pode ficar inválido e seu uso pode incorrer de acessos inválidos na memória.
Hehe, a minha é menor! rsrs
Vou colocar a sua sugestão na lista de assuntos a serem abordados! A principio seria usar um semáforo (mutex) para implementar regiões críticas encapsulando um container qualque passado por parâmetro de template. Tenho uma idéia boa sobre como fazer isso sem ter de redefinir todas as templates de containers e iterators.
Mas vou pesquisar antes no boost – talvez já exista.
Valeu!
Tenho usado muito esta implementação de lock, é rápida e eficiente.
Free Code: Win32 Lightweight Lock (http://www.agileprogrammer.com/dotnetguy/archive/2001/12/10/4485.aspx)
Bom, cada problema precisa de uma solução mas acho sempre muito importante ressaltar o perigo de colocar elementos de tipos diferentes em uma coleção.
Normalmente (nem sempre, não estou dizendo que este seja o caso) esta necessidade vem de um problema de design das classes, erro de projeto ou em algum outro ponto da especificação.
Os problemas destas soluções que acabam por levar o desenvolvedor a um cuidado que nunca será excessivo são:
1- Percorrer a coleção, como o Zimbrão citou ao falar de iteradores. E ainda que o desenvolvedor saiba que isto será um problema, acaba sendo um problema a ser tratado em mais de um ponto no código caso não se chegue a uma solução para os iteradores que esteja em conformidade com o padrão. Caso isto não seja feito, outros desenvolvedores terão que estar cientes e ficar preocupados todas as vezes que a coleção for percorrida. Mesmo que seja desenvolvido um iterador, este deverá ter um comportamento consistente com os outros iteradores da aplicação.
2- Semântica. Muitas coleções como Hashtables dependem do conceito de identidade. E a estrutura deve saber discernir entre 2 e “2″ e “dois” e “Dois” e “two”, etc, dependendo do caso e da utilização. Isto não só afeta o reuso de uma classe do domínio arquiterural (que costuma ser alto) em aplicações diferentes mas ‘as vezes em uma mesma aplicação.
O primeiro problema costuma levantar mais bugs mas é o segundo que, quando acontece, normalmente aponta para um erro de design.
Mas como eu disse, cada caso é um caso e cada problema precisa de uma solução. Se o Zimbrão precisou desta estrutura, usou e resolveu o problema, certamente esta era uma solução adequada. Logo, o exemplo é super válido, como outros comentários já apontaram. Eu só queria contribuir com uma preocupação. Não se deve usar nada indiscriminadamente, por mais versátil que seja. Para tudo é necessário ter critério e bom senso.
Concordo, um container deve ter objetos do mesmo tipo ou base na hierarquia. Mas nesse caso é isso que acontece, todos os objetos são do tipo int. O que varia é o tipo do índice, pois queria contar maçãs e também laranjas…
Mas é isso aí, antes de tudo muito planejamento sempre! E refatoração depois!
[]s