CODEWITHSUNDEEP
c++move-semantics
Akababa
Akababa

Reputation: 357

Move-initialize a priority_queue from a vector?

I saw this leetcode question and wanted to solve it with a priority queue instead of a vector (thus O(nlogk) instead of O(nk)). How do I move-initialize the priority_queue with the given vector as the underlying container? This is what I tried but I clearly misunderstood the docs because it won't compile.

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);
    }
};

Upvotes: 0

Views: 553

Answers (1)

freakish
freakish

Reputation: 56557

Did you mean

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

?

Your code fails because by default the comparer is std::less<typename Container::value_type> (so you have to explicitely write cmp in template args) and because the argument has to be an instance of cmp (not the class, actually classes are not first-class citizens in C++, you can't pass them as arguments).

Upvotes: 2

Related Questions