I would recommend the use of a smart pointer, for example std::unique_ptr (this is a C++0x feature, not all compilers support it yet). For example:
std::map<unsigned long, std::unique_ptr<Object>> map; // Do something with the map map.clear(); // The objects are automatically deleted.
You can also use std::shared_ptr (or boost::shared_ptr if your compiler doesn't support C++0x smart pointers), which has the advantage that it will work if your map can contain the same pointer more than once, and your objects won't be destroyed if someone else still has a pointer to them.
boost::ptr_map is also an options, though I believe that, like the manual approach, will not work right if the map contains the same pointer more than once.