get_priority_queue_cont.cpp

// https://leetcode.com/problems/find-k-pairs-with-smallest-sums/
// a brute-force solution, just for demonstration how to get container from priority_queue

template <class T,
          class Container = vector<T>,
          class Compare = less<typename Container::value_type> >
class priority_queue_v2 : public priority_queue<T, Container, Compare> {
public:
    using base_t = priority_queue<T, Container, Compare>;
    priority_queue_v2(const Compare& cmp)
    : base_t(cmp) {
    }
    const Container& get_underline_container() const {
        return priority_queue<T, Container, Compare>::c;
    }
};

class Solution {
public:
    vector<pair<int, int>> kSmallestPairs(vector<int> nums1, vector<int> nums2, int k) {
        using pair_t = std::pair<int, int>;
        auto cmp = [](const pair_t& lhs, const pair_t& rhs) {
            return lhs.first + lhs.second < rhs.first + rhs.second;
        };
        
        priority_queue_v2<pair_t, std::vector<pair_t>, decltype(cmp)> pq(cmp);
        
        size_t i = 0, sz = nums2.size();
        for (const auto v1: nums1) {
            for (i = 0; i < sz; ++i) {
                int v2 = nums2[i];
                if (pq.size() < k) {
                    pq.emplace(v1, v2);
                    continue;
                }
                const auto& top_v = pq.top();
                if (v1 + v2 < top_v.first + top_v.second) {
                    pq.pop();
                    pq.emplace(v1, v2);
                } else {
                    break;
                }
            }
            if (i == 0) break;
        }
        return pq.get_underline_container();
    }
};