С предоставленной информацией, это немного игра в догадки, но если вы не тасуете огромные объемы данных, это может подойти.
using entry = std::pair<std::string, int>;
using CompareFunc = bool(*)(const entry&, const entry&);
using sortset = std::set<entry, CompareFunc>;
sortset bv(themap.begin(), themap.end(), [](auto& a, auto&b){ a.second!=b.second?a.second<b.second:a.first<b.first; });
for(const auto& d : bv) {
//
}