C++ priority_queue with custom comparator and removal of any item

Question

I am working on a solution with min heap which apart from custom comparator requires support of removal of any element. A fully custom heap impl is one way to go. But I wanted to rely on C++ STL for desired operations.
C++ documentation and StackOverflow answer here pointed me to use a custom class and overload custom remove method. I also overloaded custom comparator in the same class.

template<typename T>
class custom_priority_queue_MinHeap : public std::priority_queue<T, std::vector<T>>
{
  public:
  bool remove(const T& value) 
  {
    auto it = std::find(this->c.begin(), this->c.end(), value);
    if (it != this->c.end())
    {
        this->c.erase(it);
        std::make_heap(this->c.begin(), this->c.end(), this->comp);
        return true;
    }

    return false;
  }

  bool operator()(const pair<int, int> &a, const pair<int, int> &b)
  {
    cout << "Custom comparator called" << endl;  <----------- Never called
    return a.second > b.second;
  }
};

Consumption of the custom heap looks something like:

custom_priority_queue_MinHeap<pair<int, int>> minHeap;
minHeap.push({0, 10});
minHeap.push({1, 5});
minHeap.push({2, 15});

while(!minHeap.empty())
{
    pair<int, int> p = minHeap.top();
    minHeap.pop();
    cout << p.first << " " << p.second << endl;
}

When run on Ideone, minHeap push is not working as expected. It flashes below output:

2 15
1 5
0 10

The correct output should be:

1 5
0 10  
2 15

The () comparator overload is never called which seems to be the culprit. Elements are getting popped in the order they were inserted. Interestingly, remove function is working fine.

Question(s):
Is it possible to fully rely on C++ priority_queue STL to achieve desired operations, i.e. custom comparator with support of removal of any element? If yes, is there anything I am missing in the above implementation?

Why are you deriving from `std::priority_queue`? It wasn't designed to be derived from, as the destructor is not virtual. — PaulMcKenzie, Oct 03 '19 at 18:27
@PaulMcKenzie, I am following the design from this SO thread: https://stackoverflow.com/questions/19467485/how-to-remove-element-not-at-top-from-priority-queue — Green goblin, Oct 03 '19 at 18:36
`std::make_heap(this->c.begin(), this->c.end(), this->comp);` -- So what is done to make `std::make_heap` in that call use your `operator()`? I don't see where the connection is made. In Visual Studio 2019, that function is still `std::less` when that call is made. — PaulMcKenzie, Oct 03 '19 at 18:45
Yeah, you're right. that's the issue. Is there a way to make make_heap call the overloaded `operator ()`? — Green goblin, Oct 03 '19 at 19:04
You need to fully parameterize your template. Note that `std::priority_queue` [is not a 2 parameter template class](https://en.cppreference.com/w/cpp/container/priority_queue). It's the third parameter that needs to change. — PaulMcKenzie, Oct 03 '19 at 19:08
Your code references a member `this->comp` but doesn't declare it. You need to provide a minimal reproducible example. — Brian Bi, Oct 03 '19 at 19:25

score 3 · Accepted Answer · answered Oct 03 '19 at 19:31

Thanks PaulMcKenzie for pointing me in right direction! The issue was that priority_queue in STL is three parameter class. My impl was missing the third compare class parameter.
Below change worked fine. Ideone link

class Comp
{
public:
    bool operator()(const pair<int, int> &a, const pair<int, int> &b)
    {
        cout << "Custom comparator called" << endl;
        return a.second > b.second;
    }
};

template<typename T>
class custom_priority_queue_MinHeap : public std::priority_queue<T, std::vector<T>, Comp>
{
    ...
};

C++ priority_queue with custom comparator and removal of any item

1 Answers1