I recommend using a good smart pointer, that will automatically delete the pointer in your map container.
The smart_ptr class can do this for you, and there's an example usage for map in the following link:
http://axter.com/smartptr/