Я пытаюсь написать функцию, которая создает дерево Хаффмана (как часть создания кодировки Хаффмана).
Функция получает от std::vector
от unique_ptr
с до Node
объектов, которые содержат информацию о персонаже, его частоте и левом и правом сыновьях (unique_ptr
с до Node
с).
По сути, я хочу переместить все объекты в 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))
~~~~~~ ^ ~~~~~~~
Если честно, я даже не уверен, что это проблема семантики перемещения или что-то еще, что мне не хватает, поэтому любая помощь будет принята.