I am trying to learn priority_queue concept in C++, and I came across this interview question. Although, I managed to solve this problem with a lambda function, I could not figure out how to do the same operation with a custom comparator as a function object (I think it is called as 'functor')
I really had a hard time to access 'freq' variable via function object. Is it possible to do this with a function object? if it is possible how can I do that?
class Solution {
public:
vector<string> topKFrequent(vector<string>& words, int k) {
unordered_map<string, int> freq;
for (const auto &word : words) {
freq[word]++;
}
auto compare = [&freq](const auto &left, const auto &right)
{
if (freq[left] < freq[right]) {
return true;
} else if (freq[left] > freq[right]) {
return false;
}
return left > right;
};
priority_queue<string, vector<string>, decltype(compare)> PQ(compare);
for (const auto &iter : freq) {
PQ.push(iter.first);
}
vector<string> result;
while (k--) {
result.push_back(PQ.top());
PQ.pop();
}
return result;
}
};
You can create an object explicitly like this:
struct // no need to name the type
{
unordered_map<string, int> &freq; // store variable by reference
// write operator()
bool operator()(const string &left, const string &right) const
{
if (freq[left] < freq[right]) {
return true;
} else if (freq[left] > freq[right]) {
return false;
}
return left > right;
}
} compare{freq}; // capture freq by reference