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