"Not sure what is the best solution for this"
I would say that avoiding dynamically allocated C-style array would be a good start. Maybe instead of
map<string, Base*> m;
you could use:
map<string, std::vector<Base> > m;
"when I refer to a map key for the first time, I need the "Base*" pointer already allocated for "n" elements"
You could do something like this:
std::vector<Base>& getVal(const std::string& key) {
if (m.count(key) > 0 && m[key].size() > 0)
return m[key];
m[key] = std::vector<Base>(10); // n
return m[key];
}