Why an unordered_map can be passed to a queue with pair parameter?

Question

class Solution {
public:
   
    class mycomparison {
    public:
        bool operator()(const pair<int, int>& lhs, const pair<int, int>& rhs) {
            return lhs.second > rhs.second;
        }// the paremeter is pair<int,int> **
    }; 
    vector<int> topKFrequent(vector<int>& nums, int k) {
        
        unordered_map<int, int> map; 
        for (int i = 0; i < nums.size(); i++) {
            map[nums[i]]++;
        }

       
        priority_queue<pair<int, int>, vector<pair<int, int>>, mycomparison> pri_que;// the priority_queue's paremeter is also pair<int,int>

       
        for (unordered_map<int, int>::iterator it = map.begin(); it != map.end(); it++) {
            pri_que.push(*it);// but unordered_map is passed as parameter of pri_que not pair<int,int>
            if (pri_que.size() > k) { 
                pri_que.pop();
            }
        }

      
        vector<int> result(k);
        for (int i = k - 1; i >= 0; i--) {
            result[i] = pri_que.top().first;
            pri_que.pop();
        }
        return result;

    }
};

Why is the parameter different?

My notes describe it: the parameter of the priority_queue should be a pair but an unordered_map is passed. When I run it, it is correct. Why?

The loop is iterating through each item in the map and pushing each pair into the priority queue. In this line `pri_que.push(*it);` `*it` is a `pair`, — Retired Ninja, Oct 19 '22 at 04:48
I think you have misunderstood some basic facts about iterators. Read more about them in your favourite C++ book. — molbdnilo, Oct 19 '22 at 04:52
@molbdnilo My 'favourite' C++ book was written long before the STL and iterators were invented. :-) — Adrian Mole, Oct 19 '22 at 05:14

Adrian Mole · Accepted Answer · 2022-10-19T08:54:59.043

You are confusing the STL container (in your case, a std::unordered_map) with the object(s) referred to by that container's iterator. STL containers are collections of a given type of object and each has associated iterators, which refer to particular objects within the collection. So, for example, a std:vector<int> will be a collection of int types but its iterators will provide references to the contained objects, which will be of type int. Iterators are, in many ways, like pointers, but not quite; see: Is an iterator in C++ a pointer?

For the STL "map" containers (including the unordered_map class that you are using), each object in the container is a pair, comprising a (constant) "key" and a corresponding "value". In your case, you have defined both the key and the value to be of type int – so each object in the map will be of pair<const int, int> type.

The it iterator in your first for loop will run through the map, referring ('pointing') to each of its elements in turn. When you dereference that iterator (using the * in *it) you will get the referred-to object, in each iteration of the loop. That object will, in each case, be a pair<const int, int>, so it is a valid argument for your call to pri_que.push.

Why an unordered_map can be passed to a queue with pair parameter?

1 Answers1