How to use functor as custom comparator in priority_queue

Question

I am trying to create a functor as custom comparator for my priority_queue which takes in an unordered_map as a parameter for constructor. I am not sure how to call the functor when declaring the priority_queue as I am getting the error:

"Line 22: Char 48: error: template argument for template type parameter must be a type priority_queue<string, vector, compareWords(wordFreq)> pq;"

   class compareWords{
        public:
        compareWords(unordered_map<string, int> &wordCounts): wordFreq(wordCounts){}
        bool operator()(string word1, string word2){
            if(wordFreq[word1] == wordFreq[word2]){
                return word1 < word2;
            }
            return wordFreq[word1] < wordFreq[word2];
        }
        private:
        unordered_map<string, int> wordFreq;
    };
    vector<string> topKFrequent(vector<string>& words, int k) {
        vector<string> result;
        unordered_map<string, int> wordFreq;
        for(int i = 0; i < words.size(); i++){
            wordFreq[words[i]]++;
        }
        priority_queue<string, vector<string>, compareWords(wordFreq)> pq;
        for(auto& item: wordFreq){
            pq.push(item.first);
        }
        for(int i = 0; i < k; i++){
            result.push_back(pq.top());
            pq.pop();
        }
        return result;
    }

user4581301 user4581301 · Accepted Answer · 2020-08-27T17:57:37

TL;DR version:

priority_queue<string, vector<string>, compareWords> pq(compareWords{wordFreq});

How we got there:

With the trivial solution, pass the comparator into pq's constructor, you encounter the Most Vexing Parse and

priority_queue<string, vector<string>, compareWords> pq(compareWords(wordFreq));
                                       ^class goes here ^ object goes here

is a function definition. Yuck. Normally the solution to MVP is to use "uniform initialization"

priority_queue<string, vector<string>, compareWords> pq{compareWords(wordFreq)};
                                                       ^                      ^

but this triggers priority_queue's Initialization list constructor. Also yuck.

However, we can use the curly braces on compareWords's construction instead

priority_queue<string, vector<string>, compareWords> pq(compareWords{wordFreq});
                                                                    ^        ^

and avoid priority_queue's initialization list constructor overload while not fooling the constructor into thinking we're declaring a function. Thank you to Caleth for pointing this trick out. I'd overlooked it.

How to use functor as custom comparator in priority_queue

1 Answers

TL;DR version:

How we got there: