只是为了好玩,我已经实现了可以想象的最简单的排序算法：
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将在这里做同样的事情:(有没有其他方法将数据移出树？
