c++ - 如何在包含 pair 的 Priority_queue 中查找值？

Question

通常我们可以使用 heap.find(value) 查找某个值是否存在于优先级队列中。如果它不存在，它将返回 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; }
};

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

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

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