How can I implement a fast map having multiple keys?

Constant look up requires a hash map. You can use a the boost::unordered_map (or tr1). The key would be the combined hash of the int and the void pointer.

If you don't want to use boost, you can try map< int, map<void*, vector> >. The lookups are however O(log(map size)).