برای اینکار بایستی از تابع std::find_if استفاده کنید به صورت زیر:
my_map.insert(std::pair<string, Pos>("ali", Pos(1, 1)));
my_map.insert(std::pair<string, Pos>("reza", Pos(1, 5)));
my_map.insert(std::pair<string, Pos>("hasan", Pos(2, 2)));
my_map.insert(std::pair<string, Pos>("vahid", Pos(3, 7)));
Pos search_val(2, 2);
map<string, Pos>::const_iterator res = std::find_if(my_map.begin(), my_map.end(), [&search_val](const pair<string, Pos>& pos){ return pos.second.x_ == search_val.x_ && pos.second.y_ == search_val.y_; });
cout << res->first;