c++ - 将元素移出关联容器

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 倍 :)

接下来，我想通过 move 语义提高性能:

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 算法只会调用复制构造函数。