I like Dave's idea of a freaky allocator that remembers the source of each move constructed object and automatically moves back on destruction, I'd never thought of doing that!
But here's an answer closer to your original attempt:
template<typename Iterator>
void treesort_mv(Iterator begin, Iterator end)
{
typedef typename std::iterator_traits<Iterator>::value_type element_type;
// move the elements to tmp storage
std::vector<element_type> tmp(std::make_move_iterator(begin),
std::make_move_iterator(end));
// fill the tree with sorted references
typedef std::reference_wrapper<element_type> element_ref;
std::multiset<element_ref, std::less<element_type>> tree(tmp.begin(), tmp.end());
// move data out of the vector, in sorted order
std::move(tree.begin(), tree.end(), begin);
}
This sorts a multiset
of references, so they don't need to be moved out of the tree.
However, when moving back into the original range the move assignments are not necessarily safe for self-assignment, so I moved them into a vector first, so that when re-assigning them back to the original range there will not be self-assignments.
This is marginally faster than your original version in my tests. It probably loses efficiency because it has to allocate the vector as well as all the tree nodes. That and the fact that my compiler uses COW strings so moving isn't much faster than copying anyway.