Как отсортировать список unique_ptrs? - PullRequest
0 голосов
/ 15 октября 2019

Я пытаюсь написать функцию, которая создает дерево Хаффмана (как часть создания кодировки Хаффмана).

Функция получает от 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))
          ~~~~~~ ^ ~~~~~~~

Если честно, я даже не уверен, что это проблема семантики перемещения или что-то еще, что мне не хватает, поэтому любая помощь будет принята.

1 Ответ

4 голосов
/ 15 октября 2019

std::sort требует итераторов с произвольным доступом. Ваш контейнер std::list<NodePtr> sortedFrequencies не предоставляет итераторы с произвольным доступом - только двунаправленные.

std::list имеет функцию-член с именем sort, которая будет работать для вас. См cppReference

...