9

只是为了好玩，我实现了可以想象的最简单的排序算法：

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::strings。

然后我记得关联容器从外部来看是恒定的，也就是说，std::move并且std::copy会在这里做同样的事情:(还有其他方法可以将数据移出树吗？

4

3 回答 3

8

std::set并且std::multiset只提供const对其元素的访问。这意味着您不能将某些东西移出集合。如果您可以将项目移出（或完全修改它们），则可以通过更改项目的排序顺序来破坏集合。所以 C++11 禁止它。

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

于 2013-01-20T21:11:09.287 回答
4

我相信您可以multiset为使用（第三个模板参数）创建一个自定义分配器，它实际上将其destroy方法中的元素移回用户的容器。然后擦除集合中的每个元素，并在销毁过程中将字符串移回原始容器。我认为自定义分配器需要有 2 阶段构造（将它传递给传递给您的treesort函数的开始迭代器以作为成员保存，但不是在构造期间，因为它必须是默认可构造的）。

pop显然，这会很奇怪，而且对于在 set/multiset 中没有方法是一种愚蠢的解决方法。但这应该是可能的。

于 2013-01-20T21:35:59.993 回答
0

我喜欢 Dave 的怪异分配器的想法，它可以记住每个移动构造对象的来源并在销毁时自动移回，我从没想过这样做！

但这里有一个更接近您最初尝试的答案：

template<typename Iterator>
void treesort_mv(Iterator begin, Iterator end)
{
    typedef typename std::iterator_traits<Iterator>::value_type element_type;

    // move the elements to tmp storage
    std::vector<element_type> tmp(std::make_move_iterator(begin),
                                  std::make_move_iterator(end));
    // fill the tree with sorted references
    typedef std::reference_wrapper<element_type> element_ref;
    std::multiset<element_ref, std::less<element_type>> tree(tmp.begin(), tmp.end());

    // move data out of the vector, in sorted order
    std::move(tree.begin(), tree.end(), begin);
}

这是一种multiset参考，因此不需要将它们移出树。

但是，当移回原始范围时，移动分配对于自分配来说不一定是安全的，所以我先将它们移动到一个向量中，这样在将它们重新分配回原始范围时就不会出现自分配。

在我的测试中，这比您的原始版本略快。它可能会降低效率，因为它必须分配向量以及所有树节点。那以及我的编译器使用 COW 字符串的事实，所以移动并不比复制快多少。

于 2013-01-21T00:44:14.780 回答