C++ priority queue swapping contents
c++, c++11, priority-queue
Solution
Is there a way I could possibly bend std::priority_queue to do my bidding without making it extremely ugly?
You could write a wrapper that hides the predicate and uses inheritance behind the scenes. However, that seems overkill.
If not then could I perhaps re-structure my class to do the same thing, but still use std::priority_queue?
You could wrap the access to the queues in functions. Then use a bool or integer variable to check which queue needs to be accessed.
Otherwise could I maybe re-use most of the heapify logic in the std library to achieve this?
This sounds like the best option, based on what you explained. Store each `priority_queue` in a `std::vector` and use the `std::make_heap`, `std::push_heap` and `std::pop_heap` functions to manage the heap structure. If you keep all priority queues in a `std::array<std::vector<int>, 3>`, you can use `std::rotate` to perform the logic you described. In addition, you would need to keep a boolean variable indicating which predicate to use for the heap operations.
Problem
I am writing a class which has three priority queues as private members. ``` 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. }; ``` Now I require `first` and `third` to start as `min heaps` and `second` as a `max heap`. As part of the functionality of my class I need to do the following: - Move `second` to `first`. Ideally this is achieved through lowest amount of copying. The underlying vector should just be moved. Additionally `first` should now behave like a `max heap`. - Move `third` to `second`. This means `second` should now behave like a `min heap`. - Since `third`'s contents have been moved to `second`, it should be empty. I would like to either allocate a new underlying vector or re-use `first's` underlying vector (it doesn't need it any more. Additionally third should now be a `max heap`. I need to perform this cycle (max -> min and min -> max) an unknown number of times. I am struggling to do this with `std::priority_queue` since the Comparator is a template argument which means I cannot change it at run time. This is preventing me from turning a `min heap` into a `max heap`. So my questions are: - Is there a way I could possibly bend `std::priority_queue` to do my bidding without making it extremely ugly? - If not then could I perhaps re-structure my class to do the same thing, but still use `std::priority_queue`? - Otherwise could I maybe re-use most of the `heapify` logic in the std library to achieve this?