Not bad. I think it would be a little simpler and faster with:
while (cin >> s) M[s]++;
for (map<string,int>::iterator i = M.begin(); i != M.end(); i++) {
S.insert(make_pair(i->second, i->first));
}
But maybe there's a downside to that approach that isn't obvious to me?