2

在复习算法设计和学习 C++11 的同时，我想出了以下堆排序的实现：

template <typename It, typename Comp>
void heapSort(It begin, It end, Comp compFunc, std::random_access_iterator_tag)
{
    std::make_heap(begin, end, compFunc);
    std::sort_heap(begin, end, compFunc);
}

template <typename It, typename Comp, typename IterCat>
void heapSort(It begin, It end, Comp compFunc, IterCat)
{
    typedef typename It::value_type value_type;

    std::vector<value_type> randomAccessContainer;
    randomAccessContainer.reserve(std::distance(begin, end));
    std::move(begin, end, std::back_inserter(randomAccessContainer));

    heapSort(std::begin(randomAccessContainer), std::end(randomAccessContainer), compFunc, std::random_access_iterator_tag());
    std::move(std::begin(randomAccessContainer), std::end(randomAccessContainer), begin);
}

[begin, end)首先从新容器移入新容器，然后从该容器移回新容器是标准 C++[begin, end)吗？

4

2 回答 2

2

首先从 [begin, end) 移动到新容器，然后从该容器移回 [begin, end) 是标准 C++ 吗？

我最初对您使用“标准”一词感到困惑，并编辑了问题，以便询问这是否“合法”。这个问题的答案是：“是的，这是完全合法的”。在原始范围内的元素被移出后，它们仍然处于有效（即使未指定）状态。

因此，第二次调用std::move()将只移动分配元素，并且这些元素的类型应具有不带前置条件的移动分配运算符。只要是这种情况，我认为没有问题。

但是，在编辑了您的问题后，我开始怀疑您是否真的想问这是否是“标准”，意思是“惯例”，这就是我恢复原始措辞的原因。

这个问题的答案是“部分”。您通常会使用几个移动迭代器而不是调用来初始化临时向量std::move：

std::vector<value_type> randomAccessContainer(
    std::make_move_iterator(begin),
    std::make_move_iterator(end)
    );

除此之外，您的实现对我来说似乎是正确的。

于 2013-03-09T16:18:17.873 回答
0

不，不是。

如果还没有，我可以看到您如何需要它成为随机访问容器。在这种情况下，更喜欢std::make_move_iterator：

std::vector<value_type> randomAccessContainer(
     std::make_move_iterator(begin), 
     std::make_move_iterator(end));

在所有其他情况下，您都希望就地排序。（除非您可能需要对异常“无影响”）

于 2013-03-09T16:13:29.677 回答