如何对 unique_ptrs 的列表进行排序？

Question

我正在尝试编写一个创建霍夫曼树的函数（作为创建霍夫曼编码的一部分）。

该函数接收 std::vector 个 unique_ptr 到 Node 个对象，其中包含有关字符的信息、它的频率和左右儿子（unique_ptr 到其他 Nodes).

本质上，我想做的是将所有对象移动到 std::list 如果它们的频率大于 0，然后对列表进行排序，然后继续构建树的算法（这超出了这个问题的范围）。

经过多次尝试使 std::copy_if 用于只能移动的对象后，我成功地正确使用了它，但我在对结果进行排序时遇到了问题。

在下面的代码中，NodePtr 是 std::unique_ptr<Node> 的别名，NodeVector 是 std::vector<NodePtr> 的别名：

HuffmanEncoderDecoder::NodePtr &HuffmanEncoderDecoder::buildPrefixlessTree(NodeVector &frequencies) {
    std::list<NodePtr> sortedFrequencies;

    // Copy to list only if the character appeared at least once
    std::copy_if(std::make_move_iterator(frequencies.begin()), std::make_move_iterator(frequencies.end()),
        sortedFrequencies.begin(), [](NodePtr &&node) { return node->frequency != 0; });

    // Sort the list by ascending order of frequency
    std::sort(sortedFrequencies.begin(), sortedFrequencies.end(), [](const NodePtr &n1, const NodePtr &n2)
    { return n1->frequency <= n2->frequency; });

    // ...
}

我正在使用 clang++，它输出以下错误：

error: invalid operands to binary expression ('std::_List_iterator<std::unique_ptr<HuffmanEncoderDecoder::Node,
      std::default_delete<HuffmanEncoderDecoder::Node> > >' and 'std::_List_iterator<std::unique_ptr<HuffmanEncoderDecoder::Node, std::default_delete<HuffmanEncoderDecoder::Node> > >')
      if (__last - __first > int(_S_threshold))
          ~~~~~~ ^ ~~~~~~~

老实说，我什至不确定这是移动语义问题，还是我遗漏的其他问题，因此我们将不胜感激。

Answer 1

std::sort 需要随机访问迭代器。您的容器 std::list<NodePtr> sortedFrequencies 不提供随机访问迭代器 - 仅提供双向迭代器。

std::list 有一个名为 sort 的成员函数，它对你有用。参见 cppReference

如何对 unique_ptrs 的列表进行排序？

How to sort a list of unique_ptrs?

c++

lambda

stl

move-semantics