c++lambdapriority-queuefunctorfunction-object

how to use a function object as a custom comparator for accessing a local variable instead of using a lambda function in C++?


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

Solution

  • 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