What you basically want is a copy, as std::map doesn’t keep the keys in a std::set. std::copy assumes that the value types are compatible, which isn’t the case here. The std::map::value_type is a std::pair. You want to copy only the first part of the pair, which means you need a std::transform. Now, since you will be using an insert_iterator on the set, order doesn’t matter. The std::set will sort on insertion, even though the map was already sorted.
[edit] Code might be easier. Top of my head, not compiled.
std::transform(MyMap.begin(), MyMap.end(),
std::inserter(MySet, MySet.end()),
boost::bind(&std::pair<Key,Value>::first, _1));
If you’ve got SGI’s select1st, you don’t need the boost::bind.
[edit]
Updated for C++14
std::transform(MyMap.begin(), MyMap.end(),
std::inserter(MySet, MySet.end()),
[](auto pair){ return pair.first; });