如何在存储pair<int,int>的priority_queue中查找指定元素？

Great question! The standard std::priority_queue in C++ doesn't come with a built-in find() method, and since it's implemented as a heap (not a fully sorted container), checking for the presence of a specific pair requires a bit of extra work. Let's break down your options based on whether you want efficiency or simplicity.

Option 1: Use an Auxiliary Collection (Recommended for Efficiency) #

The cleanest and most performant approach is to maintain a separate collection that tracks the keys (or full pairs) you care about in your priority queue. This lets you check for existence in O(1) or O(log n) time, depending on the collection you choose.

Example: Track by Pair's First Element #

Suppose you want to check if any pair in the queue has a specific first integer value. Here's how to do it with a std::set (for ordered lookups) or std::unordered_set (for faster average lookups):

Using std::set (Works out of the box for integers)

#include <queue>
#include <vector>
#include <set>

// Assume your comparator 'fun' is defined, e.g., for a min-heap based on pair.first
struct fun {
    bool operator()(const std::pair<int, int>& a, const std::pair<int, int>& b) {
        return a.first > b.first; // Min-heap for first element
    }
};

std::priority_queue<std::pair<int, int>, std::vector<std::pair<int, int>>, fun> min_heap;
std::set<int> tracked_first_keys; // Tracks existing first elements in the heap

// Push a pair only if its first element isn't already present
void push_if_not_exists(const std::pair<int, int>& new_pair) {
    if (tracked_first_keys.find(new_pair.first) == tracked_first_keys.end()) {
        min_heap.push(new_pair);
        tracked_first_keys.insert(new_pair.first);
    }
}

// When popping, remove the key from the tracking set
void pop_and_update() {
    if (!min_heap.empty()) {
        auto top_pair = min_heap.top();
        min_heap.pop();
        tracked_first_keys.erase(top_pair.first);
    }
}

// Check if a first element exists in the heap
bool has_first_element(int target_first) {
    return tracked_first_keys.find(target_first) != tracked_first_keys.end();
}

Using std::unordered_set (Faster average lookups, needs custom hash if tracking full pairs)

If you want to track full pairs instead of just one element, you'll need a custom hash function for std::pair<int, int> since the standard library doesn't provide one:

#include <unordered_set>

struct PairHash {
    size_t operator()(const std::pair<int, int>& p) const {
        // Combine hashes of the two integers (simple implementation)
        size_t hash1 = std::hash<int>()(p.first);
        size_t hash2 = std::hash<int>()(p.second);
        return hash1 ^ (hash2 << 1); // Shift to avoid collisions
    }
};

std::unordered_set<std::pair<int, int>, PairHash> tracked_pairs;

// Check if a full pair exists
bool has_pair(const std::pair<int, int>& target) {
    return tracked_pairs.find(target) != tracked_pairs.end();
}

Key Note: Always keep the priority queue and auxiliary collection in sync. Every push, pop, or emplace operation on the heap must update the tracking collection to avoid inconsistencies.

Option 2: Expose the Underlying Container (For Small Datasets or Debugging) #

If you don't want to maintain an extra collection, you can create a subclass of std::priority_queue to access its protected underlying container (usually a std::vector). Then you can iterate through the container to check for your target pair.

This approach has O(n) time complexity (since the heap isn't sorted), so it's only practical for small queues or one-off checks.

#include <queue>
#include <vector>
#include <algorithm>

// Custom priority queue that exposes the underlying container
template<typename T, typename Container = std::vector<T>, typename Compare = std::less<T>>
class AccessiblePQ : public std::priority_queue<T, Container, Compare> {
public:
    // Get a reference to the underlying container
    Container& get_container() {
        return this->c; // 'c' is the protected container member of std::priority_queue
    }
};

// Usage
struct fun {
    bool operator()(const std::pair<int, int>& a, const std::pair<int, int>& b) {
        return a.first > b.first;
    }
};

AccessiblePQ<std::pair<int, int>, std::vector<std::pair<int, int>>, fun> min_heap;

// Check if a pair with a specific second element exists
bool has_second_element(int target_second) {
    auto& container = min_heap.get_container();
    return std::find_if(container.begin(), container.end(),
        [target_second](const std::pair<int, int>& p) {
            return p.second == target_second;
        }) != container.end();
}

Important Notes #

• If multiple pairs can share the same key (e.g., same first element), use std::multiset or std::unordered_multiset (or a std::map to track counts) instead of a regular set to avoid losing track of duplicates.
• Adjust the lambda or hash function to target either the first or second element of the pair, depending on your requirement.

内容的提问来源于stack exchange，提问作者venkat