如何在 Pirority_queue 中找到包含 pair<int,int> 的值？

Question

通常我们可以使用heap.find(value) 来查找某个值是否存在于优先级队列中。如果它不存在，它将 return end().

现在我有一个优先级队列，它是这样定义的

priority_queue<pair<int,int>, vector<pair<int,int>>, fun> min_heap;

我想根据pair的值来判断这个pair是否存在。怎么找？

Answer 1

std::priority_queue 不允许对除顶部元素以外的元素进行任何访问，也不允许外部访问底层容器。所以如果你需要一个可迭代的优先级队列，你必须自己编写一些代码。你可以创建这样的东西：

template <class T, class Container = std::vector<T>, class Compare = std::less<typename Container::value_type>>
class IterableQueue : public std::priority_queue<T, Container, Compare>
{
public:
  using std::priority_queue<T, Container, Compare>::priority_queue;

  const Container& container() const { return this->c; }
};

请注意，一般来说，从标准库容器公开继承是个坏主意（就像我上面的示例所做的那样），因为它们没有虚拟析构函数，因此允许转换为基础容器有潜在的危险。

在生产代码中，最好使用私有继承并发布（通过 using 声明）您希望访问的成员（基本上只是所有成员）。

另请注意，让外部世界以非const方式访问底层容器将是一个非常糟糕的主意，因为它可能违反优先级队列的不变量并导致未定义的行为。

Answer 2

你可以制作一个相同类型的tmp Priority Queue，将你原来的PQ传递给构造函数来复制元素，然后当然你可以检查顶部并弹出直到找到你想要的对或新的PQ为空:

pair<int, int> wantedPair = {5, 3};
bool found = false;
priority_queue<pair<int,int>, vector<pair<int,int>>, fun> tmp(min_heap);
while(tmp.empty() == false) {
    if (wantedPair == tmp.top()) {
        found = true;
        break;
    }

    tmp.pop();
}

如果你想在不同类型的 PQ 中多次使用它，你可以为 find 创建一个模板函数。

如何在 Pirority_queue 中找到包含 pair<int,int> 的值？

How to find value in Pirority_queue which contains pair<int,int>?

c++

stl

priority-queue