Вопрос:

Переместить-инициализировать priority_queue из вектора?

c++ move-semantics

167 просмотра

1 ответ

168 Репутация автора

Я видел этот вопрос с кодом leetcode и хотел решить его с помощью приоритетной очереди вместо вектора (то есть O (nlogk) вместо O (nk)). Как переместить-инициализировать priority_queue с заданным вектором в качестве основного контейнера? Это то, что я пытался, но я явно неправильно понял документы, потому что они не компилируются.

struct ListNode {
    int val;
    ListNode *next;
    ListNode(int x) : val(x), next(NULL) {}
};

class cmp{
    public:
    bool operator()(const ListNode *a,const ListNode *b) const {
        if(b==nullptr) return false;
        return a==nullptr || a->val>b->val;
    }
};
class Solution {
    ListNode* helper(auto& lists) {
        ListNode *ans=lists.top();lists.pop();
        if(ans==nullptr) return nullptr;
        lists.push(ans->next);
        ans->next=helper(lists);
        return ans;
    }
public:
    ListNode* mergeKLists(vector<ListNode*>& lists) {
        if(lists.empty()) return nullptr;
        priority_queue<ListNode*,vector<ListNode*>> pq(cmp,std::move(lists)); //compiler says error: 'std::move' is not a type
        return helper(pq);
    }
};
Автор: Akababa Источник Размещён: 08.11.2017 10:16

Ответы (1)


1 плюс

42073 Репутация автора

Решение

Вы имеете в виду

priority_queue<ListNode*, vector<ListNode*>, cmp> pq{ cmp{}, std::move(lists) };

?

Ваш код дает сбой, потому что по умолчанию компаратором является std::less<typename Container::value_type>(так что вы должны явно писать cmpв аргументах шаблона), а аргумент должен быть экземпляром cmp(не классом, на самом деле классы не являются гражданами первого класса в C ++, вы не можете передать их в качестве аргументов).

Автор: freakish Размещён: 08.11.2017 10:28
Вопросы из категории :
32x32