如何在 priority_queue 中使用仿函数作为自定义比较器

Question

我正在尝试为我的 priority_queue 创建一个仿函数作为自定义比较器，它将 unordered_map 作为构造函数的参数。我不确定在声明 priority_queue 时如何调用仿函数，因为我收到错误：

"第 22 行：字符 48：错误：模板类型参数的模板参数必须是一个类型 priority_queue<字符串、向量、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;
    }

Answer 1

TL;DR 版本：

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

我们如何到达那里：

使用简单的解决方案，将比较器传递给 pq 的构造函数，您会遇到 Most Vexing Parse 和

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

是函数定义。呸。通常 MVP 的解决方案是使用“统一初始化”

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

但这会触发 priority_queue 的初始化列表构造函数。也恶心。

但是，我们可以在 compareWords 的构造中使用花括号来代替

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

并避免 priority_queue 的初始化列表构造函数重载，同时不让构造函数误以为我们正在声明一个函数。感谢 Caleth 指出这个技巧。我忽略了它。

如何在 priority_queue 中使用仿函数作为自定义比较器

How to use functor as custom comparator in priority_queue

c++

priority-queue

functor

TL;DR 版本：

我们如何到达那里：