>>594
struct Comp {
　bool operator()(const pair_type& a,const pair_type& b) {
　　return /* 比較結果 */;
　}
};
vector< pair<map_type::key_type, map_type::mapped_type> > v(Map.begin(),Map.end());
sort( v.begin(), v.end(), Comp() );

あるいは

set<pair_type, Comp> s(Map.begin(), Map.end());

でソート完了、で十分でないの？