например так
(писал в броузере, если где накосячил просьба не пинать)

auto fwd = map.begin();
auto rev = map.rbegin();
for(size_t i=0; i < map.size()/2; ++i, ++fwd, ++rev)
  std::swap(fwd->second,rev->second);