c++ - 高级优先队列

Question

我正在寻找 C++ 优先级队列的实现。除了STL优先级队列中的基本功能外，它还需要以下方法:

1. 它可以在推送时删除所有相同的元素(由函数确定)(类似于集合)
2. 它可以过滤掉一些元素(由另一个函数决定)。

您对如何实现它有什么建议吗？

Answer 1

您可以将 std::set 用作没有重复的优先级队列。 top 元素可以通过 rbegin() 找到。渐近复杂度与二叉堆相同:O(1) top 根据 rbegin 的标准要求，O(lg n) push 和 O(lg n) pop。不过，常数会更高。

至于过滤器，我建议您将 std::set 包装在一个类中，该类具有运行过滤的自定义 push 方法(无论如何这是个好主意)为你断言。