即使没有指定自定义比较器，pair<int,int> 的优先级队列如何工作？

Question

A std::priority_queue 使用 std::vector 作为默认容器（参考 this). For sorting on the basis of the first element in a std::vector<pair<int, int>>, we need to define our own comparison function (Reference this）。我是这样理解的。

现在，以下代码 returns 非空数组中 k 最频繁出现的元素，时间复杂度为 O(NlogK)：

class Solution {
public:
    vector<int> topKFrequent(vector<int>& nums, int k) {
        if(nums.empty())
            return vector<int>();

        unordered_map< int, int > hashMap;
        for(int i=0; i<nums.size(); i++)
            hashMap[nums[i]]++;

        priority_queue< pair< int, int >> pq;
        vector< int > result;
        unordered_map< int, int >::iterator it=hashMap.begin();

        for(it=hashMap.begin(); it!=hashMap.end(); it++) {
            //the first one is frequency and the second one is the value
            pq.push(make_pair(it->second, it->first));

            //the peculiar implementation below is because we the code to be O(NlogK)
            if(pq.size()>(hashMap.size()-k)) {
                result.push_back(pq.top().second);
                pq.pop();
            }
        }

        return result;
    }
};

此代码工作正常并被法官接受 - 但是如何呢？使用 std::vector<pair<int, int>> 作为其底层容器的 std::priority_queue 必须包含自定义比较函数，以便正确排序。那么，它是如何工作的？

Answer 1

坦率地说，它之所以有效，是因为它就是为此而设计的。

几件事：

a std::priority_queue 使用 std::less<T>，其中 T 是基础序列值类型，作为未指定覆盖时的默认比较器。
std::less<T> 针对两个 T 参数调用 operator <，解析为任何可用的最佳 and/or。

因此，如果这按照您的要求工作，没有对序列类型比较器的特殊覆盖，则必须意味着存在 std::pair<int,int> 的 operator < 将整个事情连接在一起。

确实有。检查有效执行此操作的 std::pair<T1,T2>, you'll find there is an operator < 重载的文档：

if (lhs.first < rhs.first)
    return true;
else if (!(rhs.first < lhs.first))
    return lhs.second < rhs.second
else
    return false;

有关其工作原理的思维游戏示例留给 reader 思考。

即使没有指定自定义比较器，pair<int,int> 的优先级队列如何工作？

How does a priority queue of pair<int,int> work even without specifying a custom comparator?

c++

vector

priority-queue

std-pair