将元素移出关联容器

Question

只是为了好玩,我已经实现了可以想象的最简单的排序算法:

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(), tree.end(), begin);
}

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

然后我想起关联容器是不变的来自外部的,就是std::move和std::copy将在这里做同样的事情:(是否有移动数据从树上任何其他方式？

Answer 1

std::set并且std::multiset只提供const对其元素的访问.这意味着你不能移动一些东西.如果您可以移出项目(或根本不修改它们),您可以通过更改项目的排序顺序来中断该项目.所以C++ 11禁止它.

因此,您尝试使用该std::move算法只会调用复制构造函数.