C++优先级队列交换内容

Question

我正在写一个有三个优先队列作为私人成员的班级.

class Foo {
...
...

private:
  // I am fine with using pointers instead if it helps.
  std::priority_queue<int> first;   // min heap.
  std::priority_queue<int> second;  // max heap.
  std::priority_queue<int> third;  // min heap.
};

现在我需要first并third以a min heaps和seconda 开始max heap.作为我班级功能的一部分,我需要做以下事情:

1. 移动second到first.理想情况下,这是通过最低的复制量来实现的.应该移动底层矢量.此外first,现在应该表现得像max heap.
2. 移动third到second.这意味着second现在应该表现得像min heap.
3. 由于third已将内容移至second,因此应为空.我想要分配一个新的底层向量或重用first's底层向量(它不再需要它.另外第三个现在应该是一个max heap.

我需要执行此循环(max - > min和min - > max)未知次数.

我很难做到这一点,std::priority_queue因为Comparator是一个模板参数,这意味着我无法在运行时更改它.这阻止我min heap变成一个max heap.

所以我的问题是:

1. 有没有一种方法可以弯曲std::priority_queue我的出价而不会让它变得非常难看？
2. 如果没有,那么我是否可以重新构建我的课程来做同样的事情,但仍然使用std::priority_queue？
3. 否则我可以重新使用heapifystd库中的大多数逻辑来实现这个目的吗？

Answer 1

有没有办法我可以弯曲std :: priority_queue来做我的出价而不会让它变得非常难看？

您可以编写一个隐藏谓词并在后台使用继承的包装器.然而,这似乎有点矫枉过正.

如果没有那么我可以重新构建我的类来做同样的事情,但仍然使用std :: priority_queue？

您可以将访问权限包装在函数中.然后使用bool或整数变量来检查需要访问的队列.

否则我可以重新使用std库中的大部分heapify逻辑来实现这个目的吗？

根据您的解释,这听起来像是最好的选择.每个存放priority_queue在一个std::vector和使用std::make_heap,std::push_heap以及std::pop_heap功能来管理堆结构.如果将所有优先级队列保留在a中std::array<std::vector<int>, 3>,则可以使用它std::rotate来执行所描述的逻辑.此外,您需要保留一个布尔变量,指示哪个谓词用于堆操作.