template<typename Iterator>
void treesort(Iterator begin,Iterator end)
{
    typedef typename std::iterator_traits<Iterator>::value_type element_type;
 
    // copy data into the tree
    std::multiset<element_type> tree(begin,end);
 
    // copy data out of the tree
    std::copy(tree.begin(),tree.end(),begin);
}

对于我的测试数据,它只比std :: sort慢大约20倍:)

接下来,我想通过移动语义来提高性能：

template<typename Iterator>
void treesort(Iterator begin,Iterator end)
{
    typedef typename std::iterator_traits<Iterator>::value_type element_type;
 
    // move data into the tree
    std::multiset<element_type> tree(std::make_move_iterator(begin),std::make_move_iterator(end));
    // move data out of the tree
    std::move(tree.begin(),begin);
}

但这并没有显着影响性能,即使我正在对std :: strings进行排序.

然后我记得关联容器从外部是常量,也就是说,std :: move和std :: copy将在这里做同样的事情:(有没有其他方法将数据移出树？